98 Q Theory ofComputer Science
Solution
The transition table of M is given by Table 3.25.
TABLE 3.25 Transition Table for Example 3.15
State
a
b
For the equi valent DFA:
(i) The states are subsets of Q = {qo, CJl, CJ2, Q3, Q4}'
(ii) [qo] is the initial state.
(iii) The subsets of Q containing Q3 or Q4 are the final states.
(iv) 8 is defined by Table 3.26. We start from [qoJ and construct 8, only
for those states reachable from [qoJ (as in Example 3.8).
TABLE 3.26 Transition Table of DFA for
Example 3.15
State
[qQ]
[qQ. qzl
[qQ. q4]
a
[qQ]
[qo. q4]
[qo]
b
[qQ, q2]
[qQ- qzJ
[qQ. q2]
EXAMPLE 3.16
Construct a DFA equivalent to an NDFA whose transition table is defined by
Table 3.27.
TABLE 3.27 Transition Table of NDFA for
Example 3.16
State
a
b
Solution
Let i'v! be the DFA defined by
M = C{'!"·()I·'i2· Q 3}, {a, b}, 0, [gal F)