4 ms·

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),

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!)

eru 6y ago
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 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.
bawolff 6y ago
/^$.*$\1$/ (Match all lines that are palidromes in posix BRE syntax) cannot be done with a finite state machine.
- compsciphd 6y ago
  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_chap09.html https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1... so I guess not even all posix RE can be converted to finite state machines.
- throwaway_pdp09 6y ago
  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.
  - compsciphd 6y ago
    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.
  - lgeorget 6y ago
    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 https://en.wikipedia.org/wiki/Pushdown_automaton
    - compsciphd 6y ago
      which actually pcre has, as it has "subroutines"
    - eru 6y ago
      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.
      - throwaway_pdp09 6y ago
        Ah, now that makes more sense! Original comment threw me rather. Thanks. A -> bAb where b is a terminal, ok.
  - bawolff 6y ago
    Thanks you are right, its not a palidrome. However the language it matches is still not a regular language.

eru 6y ago

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 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.

bawolff 6y ago

/^$.*$\1$/ (Match all lines that are palidromes in posix BRE syntax) cannot be done with a finite state machine.

compsciphd 6y ago
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_chap09.html https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1... so I guess not even all posix RE can be converted to finite state machines.
throwaway_pdp09 6y ago
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.
- compsciphd 6y ago
  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.
- lgeorget 6y ago
  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 https://en.wikipedia.org/wiki/Pushdown_automaton
  - compsciphd 6y ago
    which actually pcre has, as it has "subroutines"
  - eru 6y ago
    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.
    - throwaway_pdp09 6y ago
      Ah, now that makes more sense! Original comment threw me rather. Thanks. A -> bAb where b is a terminal, ok.
- bawolff 6y ago
  Thanks you are right, its not a palidrome. However the language it matches is still not a regular language.