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_{1}, a_{2}, . . . , a_{n} - then the
state that the DFA reaches after reading a_{1}, a_{2}, . . . ,
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^{n}),
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_{0})
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.