Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
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
add comment

1 Answer 1

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|improve this answer
add comment

Your Answer

 
discard

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.