Note: the author is not describing regular expressions (ie those that correspond to regular languages and nothing else), but seems to be describing some mixed beast. See eg their mention of backtracking, which is an implementation technique used in some implementations of regular expressions (where it adds nothing); and also in many implementations of not-quite-regular-expressions, where it can make a real difference.
Unix style regular expressions is what most programmers mean by regular expressions ("regular expressions" have been non-regular long before perl, fyi. Even old style unix "basic" regular expressions are irregular and i think they go back to the 80s), and is much more common than the concept in language theory that they are named after. I think its pretty obvious from context the author is talking about the common concept and not the obscure concept.
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
Note: the author is not describing regular expressions (ie those that correspond to regular languages and nothing else), but seems to be describing some mixed beast. See eg their mention of backtracking, which is an implementation technique used in some implementations of regular expressions (where it adds nothing); and also in many implementations of not-quite-regular-expressions, where it can make a real difference.
Unix style regular expressions is what most programmers mean by regular expressions ("regular expressions" have been non-regular long before perl, fyi. Even old style unix "basic" regular expressions are irregular and i think they go back to the 80s), and is much more common than the concept in language theory that they are named after. I think its pretty obvious from context the author is talking about the common concept and not the obscure concept.
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.
PCRE type is what most programmers colloquially called "regular expressions" (but I note the same thing as you in my comment below you.