3 ms·
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.
by 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 agoI 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 agoThe 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 agowhich actually pcre has, as it has "subroutines"
- eru 6y agoTo 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 agoAh, now that makes more sense! Original comment threw me rather. Thanks. A -> bAb where b is a terminal, ok.
- bawolff 6y agoThanks you are right, its not a palidrome. However the language it matches is still not a regular language.