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?
Is it always possible to convert a non-deterministic PDA to a deterministic one?
0
$\begingroup$
computer-science
automata
context-free-grammar
-
1Did you check the Wikipedia page on [deterministic PDAs](http://en.wikipedia.org/wiki/Deterministic_pushdown_automaton)? 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. – 2012-01-28
-
0grammars are used in language design. parsing simpler languages is much easier than parsing more powerful ones. Google for "LR grammars". – 2012-01-30