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?

1 / 17 Settings

<<<>>>

Let's try to determine if there is a difference between Deterministic and Non-deterministic PDAs in terms of what languages they can recognize.

q0

q1

q2

q3

a,Z;aZ

a,a;aa

b,a;λ

b,a;λ

λ,Z;Z

q0

q1

q2

q3

a,a;aa

b,Z;bZ

a,a;λ

λ,Z;Z

Saving...
Server Error
Resubmit

7.4.2. Nondeterministic CFL proof¶

1 / 10 Settings

<<<>>>

Now we want to prove that the language $L = \{a^nb^n: n \ge 1\} \cup \{a^nb^{2n}: n \ge 1\}$ is not a deterministic CFL, and therefore no deterministic PDA can recognize it.

Saving...
Server Error
Resubmit

7.4.3. Grammars for Deterministic Context-free Languages¶

1 / 15 Settings

<<<>>>

Now we know that:

• All CFLs can be generated by a CFG, and recognized by a NPDA.
• Not all CFLs can be recognized using a DPDA.
• So some CFG are associated with only non-deterministic PDAs.

Nondeterminism gives us something more in terms of capability.

Saving...
Server Error
Resubmit