Thus, M 1 either accepts both w k x and w l x or rejects both, contradicting the
assumption that and M 1 are equivalent. This contradiction proves that M 1
cannot exist .
EXERCISES
1. Minimize the number of states in the dfa in Figure 2.16.
2. Find minimal dfa's for the following languages. In each case prove that the
result is minimal.
(a) L = {a n b m > :n≥2,m≥1}.
(b) L = {a n b:n ≥0} ∪{b n a:n ≥1}
(c) L = {a n :n ≥ 0,n ≠ 3}.
(d) L = {a n :n ≠ 2 and n ≠4}.
(e) L = {a n :n mod 3 = 0}∪{a n : n mod 5 = 1}.
3. Show that the automaton generated by procedure reduce is deterministic.
4. Minimize the states in the dfa depicted in the following diagram.