- - - - - - - - - - - - - - - - -
96 };l, Theory of Computer Science
TABLE 3.23 Transition Table for Example 3.14
State/I.
a
b
-7 qa
q1
qa
q1
qa
q2
q2
q3
q1
®
q3
qa
q4
q3
C15
q5
qe
q4
qe
q5
qe
q7
qe
q3
Since there is only one final state q3' QI O = {q3}, Ql = Q - Qt Hence,
1ro = {{q3}, {qo, ql' q2' q4> % q6, q7}}' As {q3l cannot be partitioned further,
Q'I = {q3}' Now qo is I-equivalent to ql' q5, qIY but not to q2, q4, q7' and so
Q'). ={qo, ql> q5' q6}' q). is I-equivalent to Q4' Hence, Q'3 ={Q2> Q4}' The only
element remaining in Q).o is Q7' Therefore, Q4 = {Q7}' Thus,
Jrl = {{Q3}, {qo, qh qs, Q6}, {QJ., q4}, {Q7}}
Q1
2 = {Q3}
qo is 2-equivalent to q6 but not to ql or Qs. So,
Qi = {Qo, Q6}
As ql is 2-equivalent to qs,
As q). is 2-equivalent to q4,
Ql = {q)., q4},
Thus,
Jr2 = {{q3}' {qo, qd, {ql> qs}, {q)., q4}, {q7}}
Q? = {q3}
As qo is 3-equivalent to q6,
As qj is 3-equivalent to qs,
As q2 is 3-equivalent to Q4,
Ql = {q)., Q4}, Q{ = {Q7}
Therefore,
As Jr3 = Jr)., Jr2 gives us the equivalence classes. the minimum state automaton
is
M' = (Q',{a, b}, 8', q'o, F')