Lexical Analysis - Introduction to Compiler Construction in a Java World - page 46

2.7 NFA to DFA
Of course, any NFA will require backtracking. This requires more time and, because we in
practice wish to collect information as we recognize a token, is impractical. Fortunately, for
any non-deterministic finite automaton (NFA), there is an equivalent deterministic finite
automaton (DFA). By equivalent, we mean a DFA that recognizes the same language.
Moreover, we can show how to construct such a DFA.
In general, the DFA that we will construct is always in a state that simulates all the
possible states that the NFA could possibly be in having scanned the same portion of the
input. For this reason, we call this a powerset construction 3 .
For example, consider the NFA constructed for (ajb)ab illustrated in Figure 2.15. The
start state of our DFA, call it s 0 , must reflect all the possible states that our NFA can be
in before any character is scanned; that is, the NFA's start state 0, and all other states
reachable from state 0 on -moves alone: 1 and 3. Thus, the start state in our new DFA is
s 0 = f0; 1; 3g.
This computation of all states reachable from a given state s based on -moves alone is
called taking the -closure of that state.

Denition 2.5. The -closure(s) for a state s includes s and all states reachable
from s using -moves alone. That is, for a state s 2 S, -closure(s) = fsg [ fr 2

Sj; there is a path of only -moves from s to rg.

We will also be interested in the -closure over a set of states.

Denition 2.6. The -closure(S) for a set of states S includes s and all states reachable
from any state s in S using -moves alone.

Algorithm 2.1 computes -closure(S) where S is a set of states.

Algorithm 2.1 -closure(S) for a Set of States S
Input: a set of states, S
Output: -closure(S)
Stack P.addAll(S) // a stack containing all states in S
Set C.addAll(S) // the closure initially contains the states in S
while ! P.empty() do
s P.pop()
for r in m(s;) do
// m(s;) is a set of states
if r 2 C then
P.push(r)
C.add(r)
end if
end for
end while
return C

Given Algorithm 2.1, the algorithm for nding the -closure for a single state is simple.
Algorithm 2.2 does this.

3 The technique is also known as asubsetconstruction; the states in the DFA are a subset of the powerset
of the set of states in the NFA