~~~Chapter 5: Regular Sets and Regular Grammars ~ 155
The successor table is constructed as given in Table 5.4.
TABLE 5.4 Transition Table for the DFA of Example 5.13.
o
---? [qQJ
[qQ, q3]
[qQ. q4]
[qQ. q3, qtl
[qQ. q4. qt]
OQ
[qQ, q31
[qQ, q3, qt]
[qQ, q3]
[qQ, q3· qtl
[qQ, q3· qt]
[qQ, q4]
[qQ, q4]
[qQ, q4, qfl
[qQ, q4, qfl
[qQ, q4, qtl
The state diagram for the successor table is the required DFA as described by
Fig. 5.19. As qf is the only final state of NDFA [qo, q3, qf] and [qo, % qf]
are the final states of DFA
Fig. 5.19 Finite automaton of Example 5.13.
Finally. we try to reduce the number of states. (This is possible when two
rows are identical in the successor table.) As the rows conesponding to
[qo, q3' qf] and [qo, q4' qf] are identical. we identify them. The state diagram
for the equivalent automaton. where the number of states is reduced, is
described by Fig. 5.20.
°
0,1
Fig. 5.20 Reduced finite automaton of Example 5.13.
Note: While constructing the transition graph equivalent to a given I.e., the
operation (concatenation. "'. +) that is eliminated first, depends on the regular
expresslon.