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

Algorithm 2.3 NFA to DFA Construction
Input: an NFA, N = (;S;s 0 ;M;F)
Output: DFA, D = (;S D ;s D0 ;M D ;F D )
Set S D0 -closure(s 0 )
Set S D .add(S D0 )
Moves M D
Stack stk.push(S D0 )
i 0
while ! stk.empty() do
t stk.pop()
for a in do
S Di+1 -closure(m(t;a));
if S Di+1 6= fg then
if S Di+1 2 S D then
// We have a new state
S D .add(S Di+1 )
stk.push(S Di+1 )
if if + 1
M D .add(M D (t;a) = i)
else if 9j;S j 2 S D ^S Di+1 = S j then
// In the case that the state already exists
M D .add(M D (t;a) = j)
end if
end if
end for
end while
Set F D
for s D in S D do
for s in s D do
if s 2 F then
F D .add(s D )
end if
end for
end for
return D = (;S D ;s D0 ;M D ;F D )
FIGURE 2.17 An initial partition of DFA from Figure 2.16.