# Automata Theory: Building a RegExp machine

## Content:
State Machines
Formal Grammars
Implement a regular expression processor

## History:

*Pioneers:*

1951 - Stephen Kleene invented reg exp (sets).

Reuglar Langauge : Langauge recognized by a finite automata (state machines).
Kleene's Therem  : Equivalence of regular expressions and finite automata.

Has a notation named after him:
Kleene-Closure (AKA: Kleene star) : A* (Stands for repetition)

1956 - Chomsky defines his hiearchy fo grammers

Regular grammers are considered a type 3.
See: https://en.wikipedia.org/wiki/Chomsky_hierarchy

![img](https://i.imgur.com/Pj2aFeg.png)

Thus they are the weakest form of grammars.

1968 - Ken Thompson used them for pattern matching in strings, and
lexical analysis (scanners)

NFA - Thompson construction