CS Atlas GATE 2027
TOC course
0 / 91 complete

TOC/Phase 3 · CFG, PDA & Context-Free Languages

Lesson 3.3.3 · Item 56 of 91

Designing PDAs; DPDA vs NPDA; DCFL ⊂ CFL

Read at your own pace. Try the questions before opening the answers.

On this page

Recall warm-up

  1. What does empty-stack acceptance require?
    Stuck? Peek at 3.3.2 Acceptance by final state vs empty stack
    • Final state: input read, state ∈ F, stack anything. Empty stack: input read, stack empty, state anything.
    • NPDA: both conventions = CFL (convert with a new bottom marker).
    • DPDA: empty stack ⇒ only prefix-free DCFLs; final state ⇒ all DCFLs. GATE default: final state.

    Read lesson 3.3.2

  2. What is an ID of a PDA?
    Stuck? Peek at 3.3.1 Stack primer and the push-down automaton
    • PDA (Q, Σ, Γ, δ, q₀, Z₀, F); δ(q, a|ε, X) ⊆ Q × Γ*; label a, X/γ (γ = ε pop, X keep, YX push).
    • ID (q, w, γ), top first; ⊢ one move, ⊢* many.
    • Nondeterministic by default; ε-moves still see the stack.

    Read lesson 3.3.1

  3. Does nondeterminism add power to finite automata?
    Stuck? Peek at 1.2.3 Subset construction and the 2ⁿ blow-up
    • Subset construction: start {q₀} (or ECLOSE(q₀)); δ(S,a) = ⋃ δ(q,a) (then ECLOSE); accept iff S ∩ F ≠ ∅; ∅ = dead state.
    • ≤ 2ⁿ states; count only reachable sets.
    • ε-removal: δ'(q,a) = ECLOSE(δ(ECLOSE(q), a)); F' = {q : ECLOSE(q) ∩ F ≠ ∅}.
    • k-th from end is 1: NFA k+1, DFA 2ᵏ. k-th from start: DFA k+2.
    • DFA ≡ NFA ≡ ε-NFA in power.

    Read lesson 1.2.3

The Hook

For finite automata, guessing was only a convenience. For stack machines it is real power: to check that a string is an even palindrome, the machine must switch from “remembering” to “checking” exactly at the middle — and nothing in the string marks the middle. A guessing PDA tries every position; a deterministic one cannot. This lesson builds PDAs by recipe and draws the first strict line inside the context-free family.

Predict First

wcwᴿ (a c in the middle) vs wwᴿ (no marker). Which one can a PDA handle without guessing?

Core Concept

Prediction check

wcwᴿ: push until c, then pop and match. With wwᴿ the machine must guess where the middle is.

steps illustration
Same idea, one crucial difference. Step through abcba and abba.

A design recipe

  1. Decide what the stack stores (one symbol per a; the surplus of a’s over b’s; the first half).
  2. Use states for the phase (pushing, popping, done) and any finite information.
  3. Use Z₀ to detect “stack otherwise empty”.
  4. Accept with an ε-move on Z₀ into a final state.
  5. Trace one accepted and two rejected strings.
flowplay illustration
Design recipe.

Balanced parentheses and equal counts

Balanced: push X on (, pop on ), accept on Z₀. Equal #a and #b: the stack holds the surplus — A’s if a’s lead, B’s if b’s lead; a matching opposite symbol pops.

steps illustration
Two deterministic designs.

Deterministic PDAs

A PDA is deterministic (DPDA) if for every state q, input symbol a and stack top X: (1) δ(q, a, X) and δ(q, ε, X) together contain at most one move, i.e. |δ(q, a, X)| ≤ 1, and (2) if δ(q, ε, X) ≠ ∅ then δ(q, a, X) = ∅ for every a.

A language accepted by a DPDA (final state) is a deterministic context-free language (DCFL).

at most one move
for each (state, input or ε, top)
no ε-conflict
an ε-move on (q, X) forbids input moves on (q, X)
violated in wwᴿ
from q0 both “keep pushing” and “ε: guess middle” apply
The two DPDA conditions.

Regular ⊂ DCFL ⊂ CFL (both strict)

  • Every regular language is a DCFL (a DFA is a DPDA that ignores its stack). aⁿbⁿ is a DCFL but not regular.
  • Every DCFL is a CFL. wwᴿ (even palindromes) is a CFL but not a DCFL; so is { aⁿbⁿ } ∪ { aⁿb²ⁿ } and { aⁱbʲcᵏ : i = j or j = k }.
  • Every DCFL has an unambiguous grammar — but some unambiguous CFLs (like wwᴿ) are not DCFLs.

Contrast: NFA = DFA in power, but NPDA > DPDA.

CFL NPDA — palindromes wwᴿ
DCFL DPDA — aⁿbⁿ, wcwᴿ, balanced brackets
Regular DFA — a*b*
The first two strict steps of the hierarchy.

Putting it together

  • Design PDAs by deciding what the stack stores and which phase each state represents.
  • DPDAs forbid competing moves; they accept the DCFLs.
  • Regular ⊊ DCFL ⊊ CFL: guessing adds power to stack machines.

Visual

trace of abba on the wwᴿ NPDA (the accepting branch)
(q0,abba,Z) ⊢ (q0,bba,AZ) ⊢ (q0,ba,BAZ) ⊢ε (q1,ba,BAZ) ⊢ (q1,a,AZ) ⊢ (q1,ε,Z) ⊢ε (q2,ε,Z)  ACCEPT
the branch that guesses the middle after 1 symbol: (q1,bba,AZ) — b vs A: stuck. Only the right guess survives.

Worked Examples

Easy

Design a PDA for { aⁿb²ⁿ : n ≥ 0 }.

Show the full solution

On each a push AA; on each b pop one A; accept when Z₀ is on top with input finished. Trace aabbbb: stack AAAAZ, four pops, Z ⇒ accept. abbb: one extra b with Z on top ⇒ reject.

Medium

Is { aⁿbᵐ : n ≥ m } a DCFL?

Show the full solution

Yes: push for a’s, pop for b’s (reject if Z₀ appears before b’s end), accept at the end regardless of leftover A’s. No guessing needed.

GATE-level

Which are DCFLs? (i) { wcwᴿ } (ii) { wwᴿ } (iii) { aⁿbⁿ } ∪ { aⁿb²ⁿ } (iv) { aⁿbᵐcⁿ : n, m ≥ 0 }

Show the full solution

(i) DCFL (marker). (ii) not (must guess the middle). (iii) not: after reading aⁿbⁿ the machine must decide whether to stop matching or continue at ratio 2 — it would need to remember both the count and still check twice. (iv) DCFL: push a’s, skip b’s, pop on c’s. Answer: (i) and (iv).

GATE Traps

  • NFA = DFA, but NPDA ⊋ DPDA. Don’t transfer the finite-automaton result.
  • An unambiguous CFL need not be a DCFL (wwᴿ).
  • A DPDA may still have ε-moves — just never in competition with input moves on the same state and top.
  • Regular ⊂ DCFL: every regular language is deterministic context-free.

Memory Hook

A marker in the middle (c) is a signpost: the cautious traveller (DPDA) needs one; the guesser (NPDA) does not.

Connect the Dots

PDAs and CFGs both describe context-free languages — so far that is a claim. The next lesson connects them: every grammar becomes a PDA, and every PDA becomes a grammar.

Self-Test

  1. MSQ

    Which languages are DCFLs?

    1. { aⁿbⁿ }
    2. balanced parentheses
    3. { wwᴿ : w ∈ {a,b}* }
    4. { w c wᴿ }
  2. MCQ

    Which is true?

    1. NPDA and DPDA are equally powerful
    2. Every CFL is a DCFL
    3. Every DCFL has an unambiguous grammar
    4. Every unambiguous CFL is a DCFL
  3. MCQ

    A PDA has δ(q, ε, Z) = {(p, Z)} and δ(q, a, Z) = {(r, AZ)}. It is:

    1. deterministic
    2. not deterministic
    3. deterministic only if p = r
    4. not a valid PDA
  4. NAT

    In the wwᴿ NPDA, how many guesses of the middle are possible while reading a string of length 6 (positions 0…6)?

    Write your answer before opening the key.

Rule Card

  • Recipe: stack stores what is unbounded; states store the phase; Z₀ detects empty; accept via ε, Z₀.
  • DPDA: ≤ 1 move per (q, a|ε, X), and no ε-move competing with input moves.
  • Regular ⊊ DCFL ⊊ CFL. wwᴿ, aⁿbⁿ ∪ aⁿb²ⁿ, aⁱbʲcᵏ (i=j or j=k): CFL not DCFL.
  • DCFL ⇒ unambiguous grammar; not conversely.

Concept Ledger

  • deterministic PDA (DPDA)
  • deterministic CFL (DCFL)
  • NPDA
  • Regular ⊂ DCFL ⊂ CFL
  • PDA design recipe

Answer Vault

Reveal answers when you’re ready

Warm-up answers

  1. Input fully read and the stack completely empty.
  2. (state, unread input, stack top-first).
  3. No — subset construction gives an equivalent DFA.

Self-test answers

  1. ABD — No guessing needed.
    • C: Must guess the middle.
  2. C — Determinism gives a unique computation, hence an unambiguous grammar.
    • A: NPDA is strictly stronger.
    • B: wwᴿ is not.
    • D: wwᴿ is unambiguous but not a DCFL.
  3. B — ε-move and input move compete on (q, Z).
    • A: Violates condition 2.
    • C: States do not matter.
    • D: It is a valid (nondeterministic) PDA.
  4. 7 — The ε-move can be taken before any of the 7 positions.

Flashcards

  1. Is NPDA strictly more powerful than DPDA?
    Reveal answerYes (wwᴿ). Unlike NFA vs DFA.
  2. Standard CFL that is not a DCFL?
    Reveal answerwwᴿ (even palindromes).
  3. Does every DCFL have an unambiguous grammar?
    Reveal answerYes.
  4. Two DPDA conditions?
    Reveal answerAt most one move per (q, a|ε, X); no ε-move on (q, X) if there is an input move on (q, X).
ONE MORE CONNECTION MADE

Ready for the next idea?

Mark this item complete when you’ve finished reading and working through it.