Formal Labs

This lab presents intuitive examples for the objects we’ll use in this class.

Afterwards, academic and real-world uses are presented for each of them.

Automaton Example

Keep the score of a tennis match between two players. It should start at 0/0 and end when one of the players reaches 40 points.

The automaton:

tennis_automaton

Each node is a state representing the score. 15/0 means the first player has 15 points and the second one 0.

Each arrow is a transition from one state to another.

Each transition happens on an event. The first player P1 or the second one P2 can score.

The game begins in the starting state 0/0. No player has scored yet.

The game ends in one of the final states. Either P1 or P2 wins.

Note: For the sake of simplicity, we do not take into account draw events (30/30) which need further breaking.

Regular Expression Example

Check valid email addresses. [email protected] and [email protected] should be valid while person.com and [email protected] should be invalid.

The regular expression:

$(l|d)+\ @\ \ l+\ .\ (com|ro)\\ l \in \left\{ a…z \right\}, \ \ d \in \left\{ 0…9 \right\}$

$l$ represents a letter (a to z). $d$ represents a digit ( 0 to 9).

$l|d$ matches a letter or a digit.

$l+$ matches multiple letters (one or more).

$@$ and $.$ are just symbols from the email address.

Knowing this, we can now read the expression as:

some letters or numbers
followed by @
followed by some letters
followed by .
followed by com or ro

Note: For the sake of simplicity, we only match alpha-numeric email addresses ending in either .com or .ro.

Grammar Example

Decide if a sentence is correctly formed. A dog drives a bus and A dog barks are correct but Barks a bus is not.

The grammar:

$\begin{align} S & \rightarrow N V \\ N & \rightarrow N V \\ N & \rightarrow \text{dog} \ | \ \text{bus} \\ V & \rightarrow \text{drives} \ | \ \text{barks} \end{align}$

A sentence has the starting symbol S.

It is made up of two non-terminal parts of speech: a noun N followed by a verb V.

A noun N can be derived into (rewritten as) a noun N followed by a verb V.

A noun can alternatively be derived into a word: dog or bus. A verb V can be either drives or barks.

Each line in the above example is called a production.

Note: For the sake of simplicity, we ignore the preposition a and also semantically incorrect sentences such as A bus drives a dog or A dog drives a bus drives a bus.

Theoretical Usefulness

Automata:

basis for Turing Machines, used in proving the calculability and complexity of programs
appear in Artificial Intelligence (RBMs or HMMs)

Regular Expressions:

matching and extracting strings or other sequences
alternative form of an Automaton

Grammars:

compiler design

Day-to-day Applicability