4 ms·
He neglected to mention PDAs (push-down automaton) - which is basically the same concept as a DFA or NFA but with a stack. State transitions can manipulate the
by charliesome 14y ago
He neglected to mention PDAs (push-down automaton) - which is basically the same concept as a DFA or NFA but with a stack.
State transitions can manipulate the stack, and the top of a stack can be used to pick which state to move to.
PDAs aren't as powerful as Turing machines, but they are able to parse any context free grammar, so they are able to recognize languages that contain any number of 'a' characters followed by the same number of 'b' characters.
- alecbenzer 14y ago> PDAs... are able to parse any context free grammar To be complete, _non-deterministic_ PDAs can recognize any context-free language. Afaik you can't use a normal, deterministic parser to recognize things like the language of all palindromes (which is context-free).
- charliesome 14y agoAh, thanks for the correction!