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.
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.
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