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 7 A binary string (in {0, 1} ) is odd if it contains an odd number of 1s. For an integer k 1, let Sk be the language of binary strings whose suffix of length k is odd. (In other words: the string must have length at least k, and there are an odd number of 1s among its last k bits.) For example, S2 contains 01 and 110, but not 1 or 00 or 111.

Problem 7(a). Draw a DFA for S2, try to get it down to 5 states.

Problem 7(b). Argue that any DFA for Sk has at least 2k states.

Hint: Use Problem 6 with S = {0, 1} k .