Mathematical Foundation of Computer Science

DHARM

REGULAR AND NONREGULAR LANGUAGES 271

Example 10.7. Find a minimum states DFA of the finite automata shown in Fig. 10.14 which
recognizes the same language.

1 6 3 7

2

4

0

5

1

1 0 0 1

0

0

1

0

1

1

(^10)
Fig. 10.14
Sol. Find equivalence classes,
0-equivalence classes. Here we test the equivalence over the symbol ∈ and we obtain
that states 6 & 7 are equivalence so they place in the same group and all other states are
distinguishable so they place in other group, i.e., {1, 2, 3, 4, 5} and {6, 7}.
1-equivalence classes. Now we test the equivalence over the symbols ∈, 0 and 1 and we
find that there is no equivalence of states found in the first group while states 6 and 7 are
distinguishable so they are not placed in the same group, i.e., {1, 2, 3, 4, 5}, {6} and {7}.
2- equivalence classes. Test the equivalence over the symbols 00, 01, 10, 11 including the
symbols ∈, 0, and 1. Since there is no equivalence of states find in the groups further so the
minimum state DFA has 3-states and after considering of the transitions of all the states over
the alphabets we obtain the transition diagram which is shown in Fig. 10.15.
7
6
{1, 2, 3, 4, 5}
1
0
(^01)
1
0
Fig. 10.15