Conversion of an NFA into a DFA

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.

• In the transition table of an NFA, entry is a set of states;
• In the transition table of a DFA, each entry is a single state;

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: a₁, a₂, . . . , a_n - then the state that the DFA reaches after reading  a₁, a₂, . . . , a_n 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., θ(2ⁿ), 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:

ε Closure (S)

Set of states reachable from state S via epsilon.

ε Closure (T)

Set of states reachable from any state in set T via epsilon.

move (T, a)

Set of states to which there is an NFA transition from states in T on a symbol a.

Algorithm:

    initially, ε-Closure (S₀) in DTrans.
    While unmarked state T in DTrans
    mark T
    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.