Is it always possible to convert a non-deterministic PDA to a deterministic one? What is the significance of this observation for the computing power of contex-free grammars?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
The class of languages recognised by a deterministic pda is the class of deterministic context-free languages. This is a strict subclass of the class of context-free languages. An example of a context-free language that is not deterministic context-free is the language of even-length palindromes over $0$ and $1$.