distinguishable and therefore the dfa is minimal.
4. First, remove the inaccessible states q 2 and q 4 . Then use the procedure mark
to find the indistinguishable pairs (q 0 , q 1 ) and (q 3 ,q 5 ). This then gives the
minimal dfa.
6. By contradiction. Assume that is not minimal. Then we can construct a
smaller dfa that accepts . In , complement the final state set to give a
dfa for L. But this dfa is smaller than M, contradicting the assumption that M
is minimal.
10. By contradiction. Assume that q b and q c are indistinguishable. Since q a and
q b are indistinguishable and indistinguishability is an equivalence relation
(Exercise 7), q a and q c must be indistinguishable.
Chapter 3
Section 3.1
2. Yes, because ((0 + 1)(0 + 1) * ) * denotes any string of 0’s and 1’s.
6. (a) Separate into cases m = 0, 1, 2, 3. Generate 4 or more a’s, followed by the
requisite number of b’s. Solution: aaaaa * (λ + b + bb + bbb).
(c) The complement of the language in 6(a) is harder to find. A string is not
in L if it is of the form a n b m , with either n < 4 or m > 3, but this does not
completely describe . We must also consider the case where a b is
followed by an a.
10. Split into three cases: (i) m = 1, n ≥ 3, (ii) n ≥ 2, m ≥ 2, and (iii) n = 1, m ≥