Why is the conversion from nondeterministic PDA to deterministic PDA not possible?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
There are languages accepted by nondeterministic PDAs that cannot be accepted by deterministic PDAs. Perhaps the easiest way to see this is to consider inherently ambiguous context-free languages. As context-free languages, they are accepted by some nondeterministic PDA. On the other hand, every language accepted by a deterministic PDA has an unambiguous grammar, so they cannot be accepted by any deterministic PDA.
answered Apr 29, 2016 at 10:11