329
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 can have states point to each other in a loop, no?
If the set of all strings of composite length is a regular language, you can use that to prove the set of all strings of prime length are also a regular language.
But it's also easy to prove that the set of language of strings of prime length is not regular, and thus the language of strings of composite length also can't be regular.
A more formal proof.
Thank you for this. I'll review this when I can.
Yeah, but in an FSM all you have are states. To do it the obvious way, you need a loop with separate branches for every number greater than 2, or at the very least every prime number, and that's not going to be finite.