4 ms·
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 machi
by 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 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.