Deterministic finite automata
Deterministic finite automata: Nondeterministic automata are, as mentioned earlier, not quite as close to “the machine” as we would like.
Hence, we now introduce a more restricted form of finite automaton: The deterministic finite automaton or DFA for short. DFAs are NFAs, but obey a number of additional restrictions:
Ø There are no epsilontransitions.
Ø There may not be two identically labeled transitions out of the same state.
This means that we never have a choice of several nextstates: The state and the next input symbol uniquely determine the transition (or lack of same). This is why these automata are called deterministic. The transition relation if a DFA is a (partial) function, and we often write it as such: move(s;c) is the state (if any) that is reached from state s by a transition on the symbol c. If there is no such transition, move(s;c) is undefined.
It is very easy to implement a DFA: A twodimensional table can be cross indexed by state and symbol to yield the next state (or an indication that there is no transition), essentially implementing the move function by table lookup. Another (onedimensional) table can indicate which states are accepting.
DFAs have the same expressive power as NFAs: A DFA is a special case of NFA and any NFA can (as we shall shortly see) be converted to an equivalent DFA. However, this comes at a cost: The resulting DFA can be exponentially larger than the NFA. In practice (i.e., when describing tokens for a programming language) the increase in size is usually modest, which is why most lexical analyzers are based on DFAs.
A DFA represents a finite state machine that recognizes a RE. For example, the following DFA: recognizes (abc^{ })^{ }. A finite automaton consists of a finite set of states, a set of transitions (moves), one start state, and a set of final states (accepting states). In addition, a DFA has a unique transition for every statecharacter combination. For example, the previous figure has 4 states, state 1 is the start state, and state 4 is the only final state.
A DFA accepts a string if starting from the start state and moving from state to state, each time following the arrow that corresponds the current input character, it reaches a final state when the entire input string is consumed. Otherwise, it rejects the string.
The previous figure represents a DFA even though it is not complete (ie, not all statecharacter transitions have been drawn). The complete DFA is:
but it is very common to ignore state 0 (called the error state) since it is implied. (The arrows with two or more characters indicate transitions in case of any of these characters.) The error state serves as a black hole, which doesn't let you escape.
A DFA is represented by a transition table T, which gives the next state T[s, c] for a state s and a character c. For example, the T for the DFA above is:

a 
b 
c 
0 
0 
0 
0 
1 
2 
0 
0 
2 
0 
3 
0 
3 
0 
0 
4 
4 
2 
0 
4 
Suppose that we want to build a scanner for the REs:
for keyword 
= 
for 
identifier 
= 
[a  z][a  z0  9]^{*} 