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$ 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).

[email protected]$ and $.$ are just symbols from the email address.

Knowing this, we can now read the expression as:

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:

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:

Regular Expressions:

Grammars:

Day-to-day Applicability

Automata:

Regular Expressions:

Grammars: