🥞 Pushdown Automata
Why it matters: Design a PDA, decide deterministic vs nondeterministic, and relate PDAs to CFGs.
Subtopics
Each subtopic has its own page: idea, why, how, example, play, check. Mark each one understood when it clicks. 0 of 4 done.
1The PDA and how it accepts
2PDA ⇔ CFG
3Deterministic vs nondeterministic PDAs
4Designing PDAs and counting
Formulas
PDA definition
(Q, Σ, Γ, δ, q₀, Z₀, F)
Transition
δ(q, a, X) = {(p, γ)}: pop X, push γ, go to p
CFG → PDA
1 state, stack alphabet V ∪ Σ, accepts by empty stack
Power
NFA < DPDA < NPDA < (2-stack PDA = TM)
DCFL closure
closed under complement and intersection with regular; not under ∪, ∩, reversal, *
What GATE asks from this
Question types seen repeatedly in past papers. More stars means more frequent.
★★★
Which language is accepted by this PDA?
Read the transitions off a diagram or a figure; test short strings.
★★★
DPDA vs NPDA
Is the language deterministic context-free? Palindromes vs aⁿbⁿ.
★★★
Count accepted strings of a given length
Trace the PDA to count accepted strings of length n.
★★★
Equivalence with CFG / closure
Statements about PDA acceptance modes and DCFL closure.
Ratings are approximate, based on recurring patterns in past GATE CSE papers.
Previous year questions
2 real questions from the official GATE CSE papers (2020 to 2025), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.
2 questions · 0 correct of 0 attempted · marks 0 / 2
Year:
GATE 2025 CS2 · Q24MCQ1 mark
Which ONE of the following languages is accepted by a deterministic pushdown automaton?
GATE 2020 · Q10MCQ1 mark
Consider the language L = { an | n ≥ 0 } ∪ { anbn | n ≥ 0 } and the following statements. I. L is deterministic context-free. II. L is context-free but not deterministic context-free. III. L is not LL(k) for any k. Which of the above statements is/are TRUE?
Common traps
A DPDA that accepts by empty stack is weaker than one that accepts by final state.
Nondeterministic and deterministic PDAs are NOT equivalent (unlike finite automata).
A stack can be read only from the top, so it cannot compare the first half of a string with the second half in order (it reverses).