It is hard for a computer program to simulate an NFA because the transition function is multivalued. Fortunately, an algorithm, called the subset construction will convert an NFA for any language into a DFA that recognizes the same languages. Note that this algorithm is closely related to an algorithm for constructing LR parser.
The general idea behind the NFA-to-DFA construction is that the each DFA state corresponds to a set of NFA states.
For example, let T be the set of all states that an NFA could reach after reading input: a1, a2, . . . , an - then the state that the DFA reaches after reading a1, a2, . . . , an corresponds to set T.
Theoretically, the number of states of the DFA can be exponential in the number of states of the NFA, i.e., θ(2n), but in practice this worst case rarely occurs.
Algorithm: Subset construction.
INPUT: An NFA N
OUTPUT: A DFA D accepting the same language.
METHOD: Construct a transition table DTrans. Each DFA state is a set of NFA states. DTran simulates in parallel all possible moves N can make on a given string.
Operations to keep track of sets of NFA states:
While unmarked state T in DTrans
for each input symbol 'a'
do u = ε Closure (T, a)
If u is not in DTrans
then add u to DTrans
DTrans [T, a] = U
Following algorithm shows a computation of ε -Closure function.
Push all states in T onto stack.
initialize ε-Closure (T) to T
while stack is not empty
do pop top element t
for each state u with ε-edge
t to u
do If u is not in ε-Closure(T)
do add u ε Closure (T)
push u onto stack
Following example illustrates the method by constructing a DFA for the NFA.