Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.