The first portion (^.?$) matches all lines of 0 or 1 characters.
The second portion (^(..+?)\1+$) is more complicated:
(..+?) is a capture group that matches the first character in any line, followed by a smallest possible non-zero number of characters such that (2) still matches (note that the minimum length of this match is 2)
\1+ matches as many as possible (and more than 0) repeats of the (1) group
I think what this does is match any line consisting of a single character with the length
divisible by some number (due to the more than 0 condition in (2), so that there have to be repeats in the string), that’s not
1 (due to the note in (1), so that the repeating portion has to be at least 2 characters long), or
the length itself (due to the more than 0 condition in the (2), so that there is at least one repetition)
Therefore, combined with the first portion, it matches all lines of the same character whose lengths are composite (non-prime) numbers? (it will also match any line of length 1, and all lines consisting of the same string repeated more than one time)
So this is a definite example of “regex” that’s not regular, then. I really don’t think there’s any finite state machine that can track every possible number of string repeats separately.
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 1 repeated 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 1 repeated 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.
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.
So, here’s my attempt
The first portion (
^.?$) matches all lines of 0 or 1 characters.The second portion (
^(..+?)\1+$) is more complicated:(..+?)is a capture group that matches the first character in any line, followed by a smallest possible non-zero number of characters such that (2) still matches (note that the minimum length of this match is 2)\1+matches as many as possible (and more than 0) repeats of the (1) groupI think what this does is match any line consisting of a single character with the length
1(due to the note in (1), so that the repeating portion has to be at least 2 characters long), orTherefore, combined with the first portion, it matches all lines of the same character whose lengths are composite (non-prime) numbers? (it will also match any line of length 1, and all lines consisting of the same string repeated more than one time)
So this is a definite example of “regex” that’s not regular, then. I really don’t think there’s any finite state machine that can track every possible number of string repeats separately.
Yeah backreferences in general are not “regular” in the mathematical sense.
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.
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.