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. Therefore, the set of languages recognized by DFAs is the same as the set of languages recognized by NFAs.
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 has 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?
