Proof: The language consisting of strings whose lengths are prime is not regular
This is a problem that came up during my discussion with my friend for CS172: prove or disprove that the language consisting of all strings such that the length of each string is a prime number is regular. I’ll disprove this statement by showing that the pumping lemma for regular languages does not hold for this language. Because the pumping lemma holds for every regular language, the contrapositive shows that if the lemma does not hold, then the language is not regular.
Proof #
Suppose the statement is true, and the language is regular.
Then there exists a finite state automaton
that recognizes this language.
Let us call it M.
By the pumping lemma for regular languages,
there exists a natural number p such that for every string s in
Since there are infinitely many prime numbers,
there must exist a string
Now consider the string