← 🥞 Pushdown Automata
Subtopic 3 of 4

4.3Deterministic vs nondeterministic PDAs

The idea

Deterministic PDAs are weaker than nondeterministic ones: palindromes need the PDA to guess the middle.

Think of it like this: Folding a string in half to check it reads the same backwards, without knowing where the middle is.

Why it exists

It separates DCFL from CFL and decides which languages have deterministic parsers.

How it works

  1. aⁿbⁿ, wcwᴿ and balanced brackets are deterministic.
  2. wwᴿ is context-free but not deterministic (the middle is unknown).
  3. DCFLs are closed under complement but not under union, intersection or reversal.
  4. Every DCFL has an unambiguous grammar.

Worked example: abba as w wᴿ

The PDA pushes a, b, then guesses the middle and pops b, a. For abab every guess fails: rejected.

Now play with it

  • →Run abba and then abab on the palindrome PDA.
  • →Read the note under the widget about nondeterminism.

Moves (state, input, pop → state, push):

δ(q0, a, Z) → (q0, AZ)δ(q0, b, Z) → (q0, BZ)δ(q0, a, A) → (q0, AA)δ(q0, b, A) → (q0, BA)δ(q0, a, B) → (q0, AB)δ(q0, b, B) → (q0, BB)δ(q0, ε, Z) → (q1, Z)δ(q0, ε, A) → (q1, A)δ(q0, ε, B) → (q1, B)δ(q1, a, A) → (q1, ε)δ(q1, b, B) → (q1, ε)δ(q1, ε, Z) → (q2, Z)
Z
state q0
input: abba
  • Start in q0 with stack Z
  • δ(q0, a, Z) → (q0, AZ)
  • δ(q0, b, A) → (q0, BA)
  • δ(q0, ε, B) → (q1, B)
  • δ(q1, b, B) → (q1, ε)
  • δ(q1, a, A) → (q1, ε)
  • δ(q1, ε, Z) → (q2, Z)
  • ACCEPT: all input read and the PDA is in a final state

Top of stack is at the top of the box. Palindromes need NONDETERMINISM: the PDA must guess where the middle is.

Check yourself

Which language is accepted by a DPDA?

Remember: DPDA ⊊ NPDA. Palindromes need nondeterminism.
Exam notes (the dense version)

DCFL ⊊ CFL. aⁿbⁿ and wcwᴿ are deterministic; wwᴿ (palindromes) needs nondeterminism to guess the middle. DCFLs are closed under complement but not under union, intersection or reversal. Every DCFL has an unambiguous grammar.

Previous year questions: Pushdown Automata (2)

PYQs are grouped by topic, so this is the full set for Pushdown Automata; try the ones that match this subtopic. Open all 2 on the topic page.