154 g Theory ofComputer Science
(0 +1 )*(00 + 11)(0 + 1)*
r:\
}------------1~
(a)
(b)
0+1
0+1
(c)
(d)
-
qo
° 0,1
(e)
Fig.5.18 Construction of finite automaton equivalent to (0 + 1)*(00 + 11)(0 + 1)*.
Step 2 (Construction of DFA) We construct the transition table for the
NDFA defined by Table 5.3.
TABLE 5.3 Transition Table for Example 5.13
State/I
0
---) qQ
qQ, q3
qQ, q4
q3
qf
q4
qf
(q';'\
qf
qf
\ J
(0 +1 )*(00 + 11)(0 + 1)*
r:\
}------------1~
(a)
(b)
0+1
0+1
(c)
(d)
-
qo
° 0,1
(e)
Fig.5.18 Construction of finite automaton equivalent to (0 + 1)*(00 + 11)(0 + 1)*.
Step 2 (Construction of DFA) We construct the transition table for the
NDFA defined by Table 5.3.
TABLE 5.3 Transition Table for Example 5.13
State/I
0
qQ, q3
qQ, q4
q3
qf
q4
qf
(q';'\
qf
qf
\ J