Problem 3 Suppose M is a DFA, p and q are states, and a is an input symbol. Argue that if p =m q, then (p, a) =(q, a). (Advice: the contrapositive may be easier.) Problem 4 Suppose M is a DFA, L = L(M), and x and y are strings in 2*. Argue that if qm(2) =M IM(y), then x = y. (Advice: again, consider the contrapositive.) Problem 5 Suppose L, S CI*. Suppose that for every pair of distinct strings x and y in S, there is a distinguishing z (in other words, x #ly). Suppose L = L(M), for some DFA M. Argue that M has at least S states. (Hint: use Problem 4.) Remark: in the previous problem, if S is infinite then there is no DFA, so L is not regular. Problem 6 Define a "DA" (deterministic automaton) just like Sipser's 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. (For simplicity, you may suppose = {a,b}.) Problem 7 A binary string (in {0,1}*) is odd if it contains an odd number of 1's. 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 l's 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 5 with S = {0,1}k.) Problem 8 Suppose M is a DFA such that every state is reachable. That is, for each state p, there is an input string Xp such that qm(xp) = p. Furthermore, suppose that every pair of states are distinguished. Argue that M is minimal. (Hint: apply Problem 5 with S = {xp: pe Q}.) Problem 3 Suppose M is a DFA, p and q are states, and a is an input symbol. Argue that if p =m q, then (p, a) =(q, a). (Advice: the contrapositive may be easier.) Problem 4 Suppose M is a DFA, L = L(M), and x and y are strings in 2*. Argue that if qm(2) =M IM(y), then x = y. (Advice: again, consider the contrapositive.) Problem 5 Suppose L, S CI*. Suppose that for every pair of distinct strings x and y in S, there is a distinguishing z (in other words, x #ly). Suppose L = L(M), for some DFA M. Argue that M has at least S states. (Hint: use Problem 4.) Remark: in the previous problem, if S is infinite then there is no DFA, so L is not regular. Problem 6 Define a "DA" (deterministic automaton) just like Sipser's 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. (For simplicity, you may suppose = {a,b}.) Problem 7 A binary string (in {0,1}*) is odd if it contains an odd number of 1's. 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 l's 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 5 with S = {0,1}k.) Problem 8 Suppose M is a DFA such that every state is reachable. That is, for each state p, there is an input string Xp such that qm(xp) = p. Furthermore, suppose that every pair of states are distinguished. Argue that M is minimal. (Hint: apply Problem 5 with S = {xp: pe Q}.)
