Chapter 3: The Theory of Automata );J 101
TABLE 3.29 DFA of Example 3.20
State
-'>qo
q,
q2
q3
q4
®
a
b
Solution
Qp = {q)}. QJ = {qo, % q2' Q3, q-d. So, Jro = {{q)}. {qo, qi' q2' q3' q4}}
Q? cannot be partitioned further. So {q)} E JrI' Consider Qt qo is equivalent
to Ql' q2 and q4' But qo is not equivalent to q3 since 6(qo, b) = q2 and
6(q3' b) = {qsJ·
Hence.
Q
l _ {
}
1 -
Cf).
Therefore,
JrI = {{q)}, {qo. qi. q2. q4}' {q3}}
qo is 2-equivalent to q4 but not 2-equivalent to qJ or Q2'
Hence.
{qo, q4} E Jro
ql and q2 are not 2-equivalent.
Therefore.
Jr2 = {{q)}. {q3}, {qo. q4}, {qd. {qJ}
As qo is not 3-equivalent to q4, {qo. q4} is further partitioned into {qr} and
{Cf4}'
So.
Tr 3 = {{qo}, {qd. {Cf2}, {q3}, {Cf4}, {qs}}
Hence the minimum state automaton M' is the same as the given M.
EXAMPLE 3.21
Construct a minimum state automaton equivalent to a DFA whose transition
table is defined by Table 3.30.
TABLE 3.30 DFA of Example 3.21
State
-'>qo
q,
q2
®
®
q5
qs
q7
a
b