4. Question 4-Find 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 . All the words in L are of the form q" = ana..., 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 N = {, 2, 3 } SN of natural numbers such that we can write L = {a" | med} We now prove by induction on the index i of m, that L is regular: Base case For i = 1: clearly the language {m} which contains only one word, is a regu- Iar language. This langunge only contains the word " = aaa...a containing my times the letter a. We can simply define an DFA that has ms + 2 states 40, 41that will recognize this language is the initial state. There is a transition for letter a between any two consecutive states q; and 9+1, and a self-loop for state mus+ 1 for letter a. Only Gon is an accept state. Clearly this automaton accepts the word and accepts only this word. Induction hypothesis Assume that the language Lx = {0,00} is regular. Induction step We prove that if Le is regular, then so is Lx+1 = {4***, is the union of L, with the language {a}: Lx+1= L*u{a*****} 3 The language {a} is regular. This can be shown in the same way as we argued that {a} is regular in the base case). By our induction hypothesis L is regular. We have seen in class that regular langunges are closed under mions. Therefore Lx+1 is also regular. Since I the union of all the languages {0}, where mi e M, this completes the proof that L is regular. (1) Does the fact that the proof has a mistake imply that the statement is false