Problem 3 [20 pts] Consider the following inductive "proof". Explain why it is incorrect. Then discuss whether you think the claim is true or false-this can be informal and heuristic Claim Any language L over the binary alphabet containing only strings of length exactly n (where n is a positive integer) corresponds to the accepted language of some DFA with only n +2 total states. Proof We will prove the claim by induction on n Base Case We start with n = l. In this case, L must either contain a single string of length 1, eg. L = {0}, or L contains both strings of length 1, ie. L = {0, 1} If L = {0), we can design a 3-state DFA A such that L(A) = L as follows: the start state will be qstart, and we will have additional states gaccept and qreject. The only accepting state is qaccept. The transition function is defined by the following table 0 olacceptGreject lacceptreject reiect Clearly the case of L 1 is analogous If L 10, 13, we can simply change the transition function to the following 0 0 lacceptaccept dacceptGreject Greject Ireject QrejectGreject Inductive Step We can assume that the claim is true for n -1 (where n 2 2), and we wish to prove it now for n. We stregnthen our inductive hypothesis to further assume that we can design a n +1 state DFA for any language containing only strings of length n-1 such that it has a single accepting state, and also a state greject that is not accepting and such that all transitions from qreject go back to qreject- Now consider a language L containing only strings of length precisely n. Each string x E L can thus be written as ya, where y is a binary string of length n - 1, and a 10,1j. Let A be a finite automata with n +1 states that accepts exactly the length n - 1 strings y suclh that x-ya E L for some a {0, 1). Let q denote the single accepting state in A. We'll make a new automata by taking A, declaring q to no longer being an accepting state, and adding a new state qaccept that is now our only accepting state. For each a {0, 13, we will modify the transition function so that (g. a)-qaccept if x = ya for some x E L. andl(ga) = qreject otherwise. All transitions out of qaccept go to qreject. Now the resulting n + 2 state automata will accept all of the strings in L, and only the strings in L Problem 3 [20 pts] Consider the following inductive "proof". Explain why it is incorrect. Then discuss whether you think the claim is true or false-this can be informal and heuristic Claim Any language L over the binary alphabet containing only strings of length exactly n (where n is a positive integer) corresponds to the accepted language of some DFA with only n +2 total states. Proof We will prove the claim by induction on n Base Case We start with n = l. In this case, L must either contain a single string of length 1, eg. L = {0}, or L contains both strings of length 1, ie. L = {0, 1} If L = {0), we can design a 3-state DFA A such that L(A) = L as follows: the start state will be qstart, and we will have additional states gaccept and qreject. The only accepting state is qaccept. The transition function is defined by the following table 0 olacceptGreject lacceptreject reiect Clearly the case of L 1 is analogous If L 10, 13, we can simply change the transition function to the following 0 0 lacceptaccept dacceptGreject Greject Ireject QrejectGreject Inductive Step We can assume that the claim is true for n -1 (where n 2 2), and we wish to prove it now for n. We stregnthen our inductive hypothesis to further assume that we can design a n +1 state DFA for any language containing only strings of length n-1 such that it has a single accepting state, and also a state greject that is not accepting and such that all transitions from qreject go back to qreject- Now consider a language L containing only strings of length precisely n. Each string x E L can thus be written as ya, where y is a binary string of length n - 1, and a 10,1j. Let A be a finite automata with n +1 states that accepts exactly the length n - 1 strings y suclh that x-ya E L for some a {0, 1). Let q denote the single accepting state in A. We'll make a new automata by taking A, declaring q to no longer being an accepting state, and adding a new state qaccept that is now our only accepting state. For each a {0, 13, we will modify the transition function so that (g. a)-qaccept if x = ya for some x E L. andl(ga) = qreject otherwise. All transitions out of qaccept go to qreject. Now the resulting n + 2 state automata will accept all of the strings in L, and only the strings in L
