Chapter 5: Regular Sets and Regular Grammars ~ 157
Step 2 (Construction of DFA) For the NDFA given in Fig. 5.18(e). the
corresponding transition table is defined by Table 5.5.
TABLE 5.5 Transition Table for Example 5.14
StatelI
0
---0> qo
q3
q1, q2
q1
qr
q2
q3
q3
q3
qr
®
The successor table is constructed and given in Table 5.6.
In Table 5.6 the columns corresponding to [qtJ and 0 are identical. So we
can identify [qtJ and 0.
TABLE 5.6 Transition Table of DFA for Example 5.14
Q
Q o
Q 1
---0> [Qo]
[q3]
[q1, q2]
[q3]
[q3]
[qr]
[q1' Q2]
[qrJ
[q3]
@
0
0
0
0
0
The DFA with the reduced number of states corresponding to Table 5.6
is defined by Fig. 5.22.
o
o
o
Fig. 5.22 Reduced DFA of Example 5.14.
5.2.6 EQUIVALENCE OF Two FINITE AUTOMATA
T\vo finite automata over L are equivalent if they accept the same set of strings
over L. When the two finite automata are not equivalent, there is some string