5. Show that if L is a nonempty language such that any w in L has length at least
n, then any dfa accepting L must have at least n + 1 states.
6. Prove or disprove the following conjecture. If M = (Q,Σ,δ,q 0 ,F) is a minimal
dfa for a regular language L, then = (Q, Σ,δ,q 0 ,Q – F) is a minimal dfa for
7. Show that indistinguishability is an equivalence relation but that
distinguishability is not.
8. Show the explicit steps of the suggested proof of the first part of Theorem
2.4, namely, that is equivalent to the original dfa.
9. Prove the following: If the states q a and q b are indistinguishable, and if q a and
q c are distinguishable, then q b and q c must be distinguishable.
* 10. Show that given a regular language L, its minimal dfa is unique within a
simple relabeling of the states.