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:

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:

• 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:

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

Automata:

• video game states
• character animation

Regular Expressions:

• extracting parameters from an url (eg: 00123 from book-shop.com/book_00123/details)
• validating form input (eg: valid card number, name long enough etc)

Grammars:

• natural language queries (eg: what's the weather today?)