4. Question 4Find the mistake in the proof Now we let = = {a} be a unary alphabet, that is, it contains only one letter. Consider the following statement: All languages over alphabet are regular. (a) Find the mistake in the following proof for the statement: Proof. Let L be some language over alphabet E. All the words in L are of the form am = aaa ... a, that is, every word in L is simply a sequence of m times the letter a for some natural number m. Thus, there exists a set M = {M1, M2, M3, ...} CN of natural numbers such that we can write L = {a" | me M}. We now prove by induction on the index i of m that L is regular: Base case For i = 1: clearly the language {ami} which contains only one word, is a regu- lar language. This language only contains the word ami = aaa...a containing m times the letter a. We can simply define an DFA that has mi + 2 states 90,91, ...,9m1+1 that will recognize this language. qo is the initial state. There is a transition for letter a between any two consecutive states q; and 4j+1, and a self-loop for state 9m1+1 for letter a. Only qm is an accept state. Clearly this automaton accepts the word ami and accepts only this word. Induction hypothesis Assume that the language Lk = {ami, ama, amk } is regular. Induction step We prove that if Lk is regular, then so is Lk+1 = {ami amk, amk+1 +1}. Lk+1 is the union of Lk with the language {ak+1}: ', ama Lk+1 = LkU{ak+1}. For l = 1! clearly the language ta which contains only one word, is a regu- lar language. This language only contains the word a"i = aaa ... a containing my times the letter a. We can simply define an DFA that has m + 2 states 90,91, ...,9m+1 that will recognize this language. qo is the initial state. There is a transition for letter a between any two consecutive states q; and q;+1, and a self-loop for state (m+1 for letter a. Only qmi is an accept state. Clearly this automaton accepts the word ami and accepts only this word. Induction hypothesis Assume that the language Lk {ami, ama ,a"*} is regular. Induction step We prove that if Lk is regular, then so is Lk+1 = {ami, 2,..., amk, amk+1}. Lk+1 is the union of Lk with the language {a"k+1}: , ama Lk+1 Le U{ark+1}. 3 The language {amk+1} is regular. This can be shown in the same way as we argued that {ami} is regular (in the base case). By our induction hypothesis Lk is regular. We have seen in class that regular languages are closed under unions. Therefore Lk+1 is also regular. Since L is the union of all the languages {ami}, where mi e M, this completes the proof that L is regular. (b) Does the fact that the proof has a mistake imply that the statement is false