next up previous
Next: LEX Up: Lexical Analysis Previous: RE -> NFA

NFA -> DFA

NFAs easy to construct, difficult to implement.

Figure 3.34: NFA for (a|b)*abb

DFAs easy to implement (Figure 3.27, harder to construct.

For each NFA, a DFA (with unique exit states) can be constructed which accepts the same language as the NFA.
Example: DFA 3.28 accepts the same regular expression as NFA 3.24.

Fig3_28.gif
Figure 3.28: DFA for (a|b)*abb

Algorithm 3.20:Subset Construction - Given NFA, construct DFA in which each DFA state represents a subset of all NFA states.

Closure operations applied to NFA states to form DFA states shown in Figure 3.31.

Fig3_31.gif
Figure 3.31: Operations on NFA states

Figure 3.33: Computing closure(T)

Figure 3.32: Subset construction algorithm

Example: Subset Construction algorithm applied to NFA 3.34.

Figure 3.35: Transition table Dtran from NFA 3.34

Figure 3.36: DFA from NFA 3.34


next up previous
Next: LEX Up: Lexical Analysis Previous: RE -> NFA
CS 631 Class Account 2009-10-13