Definitions Suppose M = (Q, , , q0, F) is a DFA, as defined by Sipser. Given state p Q and input string x , let (p, x) denote the state that we reach, if we start in state p and then read string x. Define the function qM : Q by the rule qM(x) = (q0, x). That is, qM maps string x to the state that M would reach after reading the input x. In particular, the language accepted by M is L(M) = {x : qM(x) F}. Two DFAs are equivalent if they have the same input alphabet and they accept the same language. A DFA is minimal if there is no equivalent DFA with fewer states. Suppose we have a language L and two strings x, y (not necessarily in L). Define x and y are L-equivalent to mean: for all z , xz L yz L. We denote this by x L y. If x and y are not L-equivalent, then there is a string z such that exactly one of the two strings xz, yz is in L. We call this z a distinguishing suffix for x and y. Similarly, in a DFA, two states p and q are distinguished by string z if exactly one of the states (p, z), (q, z) is in F. If there is no such z, then we say the two states are indistinguishable.

Problem 8 Suppose M is a DFA with two indistinguishable states p and q. First, demonstrate how to construct a smaller equivalent DFA M0 . Second, argue that your M0 is equivalent to the original M (this argument should be some kind of induction).