_ _ _--=C=..:h=..:a~p=_t=_=_er 5: Regular Sets and Regular Grammars ~ 159
Solution
The initial states in ",vI and [,yI' are CJ1 and q.... respectively. Hence the first
element of the first column in the comparison table must be (q 1. q...). The first
element in the second column is (ql. CfJ,) since both CJi and CJ4 are c-reachable
from the respective initial states. The complete table is given in Table 5.7.
TABLE 5.7 Comparison Table for Example 5.15
(q. q',
(q •. q4)
(q2 q5)
(q3 q6)
(q2· q~)
(qd. q') 0,
(q2 q5)
(q,. q4)
lQ3· q6)
(q,. q4)
As we do not get a pair (q, CJ' ), where Cf is a final state and q' is a nonfinal
state (or vice wrsa) at every rO\v, we proceed until all the elements in the
second and third COIUIIl.l1S are also in the first column. Therefore. M and J'vY
are equivalent.
EXAMPLE 5.16
Shm" that the automata IvI l and [\iI: defined by Fig. 5.24 are not equivalent.
c
(a)
(b)
Fig. 5.24 (a) Automaton M, and (b) automaton M 2 ,
Solution
The initial states in !'vII and M: are ql and q.... respectively. Hence the first
column in the comparison table is (ql' Cf4)' Cfc and Cf~ are d-reachable from Cfl
and q.... We see from the comparison table given in Table 5.8 that CJl and Cfr,
arc d-reachable from Cf: and Cfe;, respectively, As Cfl is a final state in Nit. and
Cf6 is a nonfinal state in Al c . we see that M l and l\il c are not equivalent: we can
also note that Cfl is dd-reachable from qj, and hence dd is accepted by MI' dd
is not accepted by M: as only Cfro is dd-reachable from Cj.'" but CJ6 is nonfinal.