4. Question 4Find the mistake in the proof Now we let S = {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 a = 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" | MEM}. We now prove by induction on the index i of mi 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 mi times the letter a. We can simply define an DFA that has mi + 2 states 90,91, ..., 4m+1 that will recognize this language. qo is the initial state. There is a transition for letter a between any two consecutive states qj and qj+1, and a self-loop for state 2m +1 for letter a. Only (my is an accept state. Clearly this automaton accepts the word ami and accepts only this word. Induction hypothesis Assume that the language Lk = {a" amk} is regular. Induction step We prove that if Lk is regular, then so is Lk+1 = {ami, a +1}. Lk+1 is the union of Lk with the language {amk+1}: , ama mi mk+ Lk+1 = Lk U{ak+1}. 3 The language {amk+1} is regular. This can be shown in the same way as we argued that {am} 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 EM, this completes the proof that L is regular. (b) Does the fact that the proof has a mistake imply that the statement is false