337
Oh boy what a beautiful regex. I'm sure it does something logical and easy to understand.
(lemmy.world)
^.?$|^(..+?)\1+$
Matches strings of any character repeated a non-prime number of times
You got downvoted here but you're absolutely right. It's easy to prove that the set of strings with prime length is not a regular language using the pumping lemma for regular languages. And in typical StackExchange fashion, someone's already done it.
Here's their proof.
Claim 1: The language consisting of the character
1repeated a prime number of times is not regular.A further argument to justify your claim—
Claim 2: If the language described in Claim 1 is not regular, then the language consisting of the character
1repeated a composite number of times is not regular.Proof: Suppose the language described in Claim 2 is regular if the language described in Claim 1 is not. Then there must exist a finite-state automaton A that recognises it. If we create a new finite-state automaton B which (1) checks whether the string has length 1 and rejects it, and (2) then passes the string to automaton A and rejects when automaton A accepts and accepts when automaton A rejects, then we can see that automaton B accepts the set of all strings of non-composite length that are not of length 1, i.e. the set of all strings of prime length. But since the language consisting of all strings of prime length is non-regular, there cannot exist such an automaton. Therefore, the assumption that the language described in Claim 2 being regular is false.
By now, I have just one, so thanks for the assist. There's always that one (sometimes puzzling) downvote on anything factual.
The pumping lemma, for anyone unfamiliar. It's a consequence of the fact an FSM is finite, so you can construct a repeatable y just by exhausting the FSM's ability to "remember" how much it's seen.