I think (perhaps incorrectly) that posix regular expressions can be converted to finite state machines (and in fact, that is how you make them run efficiently), it is the PCRE that cannot be fully converted to finite state machines. (but willing to be corrected on this!)
Yes. Though there's lots of other flavours as well.
There's a few interesting additions you can make to POSIX style regex that preserve the linear runtime: eg complement, difference or intersection of regular expression, see eg https://docs.rs/regex/1.3.9/regex/#syntax
And there's lots of other backtracking-mandatory features that you see in some non PCRE flavours.
That will match 'abab' for example but a palindrome is not that, it reads the same forward as backward, so 'abba' is a palindrome but your rex won't match it.
I don't think a state machine can do it as it needs to remember the captured part, but not sure. Fairly sure capture groups can't be FSMs.
The language of palindroms over a finite alphabet is described by a deterministic context-free grammar, you need a pushdown automaton (i.e. a finite state machine with a stack) to recognize it.
To be more precise, you'd need to say that the palindrome is not only described by a deterministic context-free grammar, but that it is _not_ described by anything simpler.
Multiple different grammars can define the same language. There are context free grammars for regular languages.
Comments
I think (perhaps incorrectly) that posix regular expressions can be converted to finite state machines (and in fact, that is how you make them run efficiently), it is the PCRE that cannot be fully converted to finite state machines. (but willing to be corrected on this!)
Yes. Though there's lots of other flavours as well.
There's a few interesting additions you can make to POSIX style regex that preserve the linear runtime: eg complement, difference or intersection of regular expression, see eg https://docs.rs/regex/1.3.9/regex/#syntax
And there's lots of other backtracking-mandatory features that you see in some non PCRE flavours.
/^\(.*\)\1$/
(Match all lines that are palidromes in posix BRE syntax) cannot be done with a finite state machine.
That will match 'abab' for example but a palindrome is not that, it reads the same forward as backward, so 'abba' is a palindrome but your rex won't match it.
I don't think a state machine can do it as it needs to remember the captured part, but not sure. Fairly sure capture groups can't be FSMs.
I believe you need capture group back references and recursion on the capture group back references to match a palindrome
edit: actually, even with recursive construct (at least in PCRE) I think its still impossible.
The language of palindroms over a finite alphabet is described by a deterministic context-free grammar, you need a pushdown automaton (i.e. a finite state machine with a stack) to recognize it.
https://en.wikipedia.org/wiki/Pushdown_automaton
To be more precise, you'd need to say that the palindrome is not only described by a deterministic context-free grammar, but that it is _not_ described by anything simpler.
Multiple different grammars can define the same language. There are context free grammars for regular languages.
Ah, now that makes more sense! Original comment threw me rather. Thanks.
A -> bAb where b is a terminal, ok.
which actually pcre has, as it has "subroutines"
Thanks you are right, its not a palidrome. However the language it matches is still not a regular language.
I believe (perhaps wrong again) that back references are not in posix (though many implementations have them)
edit: I was wrong. back references are in posix. https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1...
so I guess not even all posix RE can be converted to finite state machines.