7.4. Deterministic Pushdown Automata¶
7.4.1. Deterministic Pushdown Automata¶
We know that non-determinism adds no real power to DFAs. That is, every NFA has an equivalent DFA.
How about for PDAs? We have introduced the concept of non-determinism to PDAs (we call these NPDAs), and we have shown that every CFG as an equivalent NPDA, and vice versa. Thus, NPDAs can recognize all CFL.
But, what about the distinction between deterministic and non-deterministic PDAs? Does non-determinism add real power to the PDA?
