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 4 Suppose M is a DFA, L = L(M), and x and y are strings in . Argue that if states qM(x) and qM(y) are indistinguishable, then x L y. (See the definitions above. It may be easier to argue the contrapositive, because then you have a specific z.)

Problem 5 Define a DA (deterministic automaton) just like Sipsers DFA, except we allow the state set Q (and its subset F) to be infinite. Argue that every language L equals L(M) for some DA M. (Try Q = . For simplicity, you may suppose = {a, b}.)