102 ~ Theory or Computer Science
Solution
Q? = {q3' (r~}, Q~ = {qo. ql' q2' q), q6' q7}
1fo = {{Q3, q4}, {qo. qj, Q2, qs, q6' q7}}
q3 IS I-equivalent to q4' So, {q3' q4} E 1f1'
qo is not I-equivalent to ql, q2, Cis but q() is I-equivalent to Q6'
Hence {q(). qd E 1f 1 . ql is I-equivalent to q2 but not I-equivalent to
qs, q6 or q7' So, {Ql' C!2} E 1f1'
qs is not I-equivalent to q6 but to q7' So, {Cis, q7} E 1f J
Hence,
Jrl = {{q3' CJ4}' {q(), qe,}, {ql' q2}, {q5' (j7}}
q3 is 2-equivalent to q4' So, {q3, q4} E Jr2'
qo is not 2-equivalent to Q6' So. {qo}· {CJ6} E Jr2'
qJ is 2-equivalent to q2' So. {qj, Q:J E Jr~.
qs is 2-equivalent to q7. So, {qs, q7} E Jr2'
Hence.
q3 is 3-equivalent to q4; qj is 3-equivalent to q2 and Cis is 3-equivalent to qi'
Hence.
As Jr3 = Jr2' the minimum state automaton is
where 8/ is defined by Table 3.31.
TABLE 3.31 Transition Table of OFA for
Example 3.21
Slate
a
b
[qo]
[q1. q2]
[q1' q2]
[q1 q2]
[q3, q4]
[Q3, q4]
[q3, q4]
[qs, q7]
[qs]
[qs. q7]
[q3. q4]
[qs]
[qs]
[qs]
[qs]