Problem Solving in Automata, Languages, and Complexity

2.4 Converting an NFA to a DFA 47

0 a

Figure 2.29: Converting an NFA to a DFA.

Solution. We construct the DFA M’ as follows:
Step 1. We let QE = E-closure({qo}) as the initial state, and let F’ = 0 be
the set of final states. Let Q’ = {QE}. If QE n F # (8, then add QE to F’.
Step 2. Repeat the following until S’( QX, a) is defined for all Qx E Q’ and
all a E (0, 1):

(1) Select Qx E Q' and a E (0, 1) such that S(Q$, a) is not yet defined.

(2) Let Qm = J(Qma).

(3) If Qm 4 Q’, then add Qm to Q’, and also add it to F’ if Qza n F # 0.

The whole process for this example is shown in the following table.

Qo = (40, ql> ad {ao, a> q5) = Qo (40,41>^427 q4)

&I = {qo, ql, qd {Qo, Ql, 43, q41!?5) {qo, 41, qd = &I

QOI = {ao, ql> 42, q4) {Qo, Ql, !I31 !I47 !I51 {qo, 41, qd = &I

&lo = {qo, 41, q3, q4, qs} (40, ql, m q4> ad = &lo {a> q1, a, qd = Qol

Note that, in Step 2, we did not have to consider states QOO, Qooo, Qoor, and

so on, since Qoo = Qo and so Qooo = Qoo = Qo and Qool = Qol. Similarly,

since &II = Qr, we do not need to consider Qrrzu for any ul E {O,l}*.

The transition diagram of the DFA M’ is shown in Figure 2.29(b). (We

write (& i2,... , im) inside a vertex to denote the state {qil, qiz,... , ai,}.) q

Example 2.24 Construct a DFA which is equivalent to the NFA M = ({p, q,

r), {(Al}, 4 PJ {CL r)>, whew

s

P

4

r

I 0 1

{P,ql IPI

• { 1 r


• 
  
  
  
  •