# Is it always possible to convert a non-deterministic PDA to a deterministic one?

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?

-
Did you check the Wikipedia page on deterministic PDAs? It states that nondeterministic PDAs are strictly more powerful than deterministic, but does not explicitly give a counterexample. See Sipser's book for details. // I do not understand your second question. – Srivatsan Jan 28 '12 at 8:25
grammars are used in language design. parsing simpler languages is much easier than parsing more powerful ones. Google for "LR grammars". – Kaveh Jan 30 '12 at 6:14

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

-