- We compile a regular expression into a recognizer by constructing a generalized transition diagram called a finite automata
- A finite Automata or finite state machine is a 5-tuple(S,∑,S0,F,δ) where S is finite set of states
∑ is finite alphabet of input symbol
S0 ∈ S (Initial state)
F (set of accepting states)
δ is a transition function
- There are two types of finite automata,
- Deterministic finite automata (DFA) have for each state (circle in the diagram) exactly one edge leaving out for each symbol
- Nondeterministic finite automata (NFA) are the other kind. There are no restrictions on the edges leaving a state. There can be several with the same symbol as label and some edges can be labeled with ε.