Pushdown automata, stacks and acceptance
Goals and acceptance contract
Use a stack to compare unbounded counts and understand the CFG–PDA correspondence. Unless explicitly restricted, PDA means nondeterministic PDA (NPDA). A configuration is (q,w,γ): current state, unread input, stack content. We write the stack top on the left. A transition (q,a,X)→(r,β) consumes a, pops top X and replaces it by β; a may be ε, consuming nothing. With stack γ=Xη the new stack is βη. These are notation conventions, not extra computational power.
Acceptance by final state means some finite computation consumes all input and ends in a final state, with any stack content. Acceptance by empty stack means some finite computation consumes all input and leaves an empty stack, with any state. Neither accepts just because a final state or empty stack occurs before the input is consumed. For NPDAs the two modes recognize exactly the CFLs, using suitable machine conversions; they are not necessarily equivalent for the same unchanged machine.
1. Worked NPDA for a^n b^n
Let Z be a bottom marker, A a count marker, and states push,pop,accept. Start in push with stack Z. On each a in push, push an A: replace X by AX for X=A or Z. On the first b, switch to pop and remove one A. In pop each b removes one A; no a-transition exists. When Z is exposed, an ε-move to accept is possible. Include this move from push as well to accept ε. The accept state has no outgoing transitions. Acceptance is by final state after complete input consumption.
Trace aabb: (push,aabb,Z)→(push,abb,AZ)→(push,bb,AAZ)→(pop,b,AZ)→(pop,ε,Z)→(accept,ε,Z). For aab, one A remains, so no acceptance. For abb, the second b finds Z and has no matching pop. For aba, an a appears in pop mode and cannot be consumed. The early ε-move from push with stack Z cannot incorrectly accept a nonempty word, because unread input remains.
Correctness invariant: in push mode the stack counts all a symbols read; in pop mode it counts unmatched a symbols after the b phase begins. Requiring Z after all input forces equal counts and the two phases enforce a-block before b-block.
2. Guessing a midpoint
For even-length palindromes {ww^R:w∈{0,1}*}, an NPDA pushes a first segment, nondeterministically guesses its end via an ε-move, then matches each remaining input symbol against the stack top. It accepts when the whole input is consumed and the bottom is reached. A wrong midpoint guess fails; an accepting guess exists exactly for a palindrome. For a marked language {w#w^R}, the # explicitly tells the machine when to switch phases, allowing a deterministic stack strategy. Do not use a deterministic strategy for an unmarked midpoint merely by saying “switch at the middle”: the location is not supplied online.
3. Simulating a grammar with a stack
For a CFG, initially place its start variable on the stack. If top A is a variable, nondeterministically replace it by a production's right side without reading input. If top a is a terminal, match and consume input a while popping it. Accept by empty stack after all input is consumed. With top on the left, replacement A→XYZ places X at the top; an implementation that pushes one symbol at a time pushes Z,Y,X in that order.
For S→aSb|ε and input ab: stack S becomes aSb; match a leaving Sb; use S→ε leaving b; match b leaving empty. This mimics a leftmost derivation. Conversely, a PDA can be converted into a CFG whose variables summarize stack-removal computations between states. The two translations establish CFGs and NPDAs as equivalent language models.
4. Determinism caveats
A DPDA cannot offer competing transitions for the same configuration. In particular, if an ε-transition is available for a state/top pair, input-consuming transitions for that same pair are excluded in the standard definition. DPDAs recognize a proper subclass of CFLs. Final-state and empty-stack deterministic acceptance are not interchangeable without additional conventions; for example, empty-stack acceptance without an endmarker imposes prefix restrictions. The NPDA equivalence must not be silently transferred to DPDAs.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. Under final-state PDA acceptance, which condition is essential?
A. Stack must be empty B. All input consumed and final state reached C. Every branch must accept D. Final state visited at any time
Answer: B
A: Final-state mode permits nonempty stack.
B: Both full consumption and finality are required.
C: NPDA acceptance is existential.
D: A visit with unread input is insufficient.
P02. With top on the left, replacing X by AB in stack XZ yields:
A. ZAB B. ABZ C. BAZ D. XZAB
Answer: B
A: This puts the replacement below Z.
B: AB replaces X while Z remains below.
C: This reverses the stated replacement.
D: X must be removed, not retained.
P03. Why does the worked PDA reject abb?
A. It cannot push A B. The first b is forbidden C. The second b has no A to pop D. Its input length is always required to be four
Answer: C
A: The initial a does push A.
B: The first b switches to pop and removes A.
C: Only Z remains before the second b.
D: No fixed length-four condition exists.
P04. The # in w#w^R primarily provides:
A. A finite upper bound on |w| B. An explicit phase-switch point C. A second stack D. Automatic acceptance of every suffix
Answer: B
A: w remains unbounded.
B: It tells the PDA when to begin matching.
C: Only one stack is needed.
D: The reversed suffix must still match.
P05. When simulating A→XYZ by individual pushes with leftmost top, push in order:
A. X,Y,Z B. Z,Y,X C. Y,X,Z D. No order can represent it
Answer: B
A: That leaves Z on top.
B: Pushing in reverse leaves X on top.
C: That leaves Z on top with the wrong remainder.
D: A stack readily represents the right side.
P06. Which statement is valid without extra deterministic conventions?
A. All CFLs have DPDAs B. Every NPDA is already a DPDA C. NPDA final-state and empty-stack modes have equal language-class power D. Flipping DPDA finals always complements immediately
Answer: C
A: DPDAs recognize a proper subclass.
B: Nondeterministic choices can be essential.
C: Machine conversions establish equivalence for NPDAs.
D: Halting/input-consumption and acceptance conventions need care.
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire Theory of Computation syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in