Prove that L={ all strings of 1’s whose length is prime} is not regular. i.e., L={1^2,1^3 ,1^5 ,1^7 ,1^11 ,—-}

Suppose the statement is true, and this langauge is regular. Then there exists a FSA(finite state automaton) that recognizes this language, which we call M. The pumping lemma says that there exists a natural number p such that for every string s in L(M) of length at least p, there is a decompositon of s=xyz such
|y| > 0
|xy| <= p
Now, we can assume that there is a string w in L(M) such that |w|=k is the first prime number greater than p since there are infinitely many prime numbers. Because w is in L(M) and |w| > p, w can be decomposed as w=xyz that satisfies the above conditions.

Now consider the string . By the condition 3 above, v is in L(M). Thus, the length of v must be a prime number. But . Clearly, k | k(1+|y|) and k > 1. Hence |v| is not prime. This contradiction implies that the supposition is false, and the given langauge is not regular.

Leave a Reply