Questions: Pushdown Automata

Question 1

A PDA attempts to recognize {ww^R} — strings of the form 'abba', 'aabbaa', etc. (a word followed by its reverse). Why must this PDA be nondeterministic?

• A. Because the PDA needs two stacks to store both halves simultaneously
• B. Because the PDA must guess where the midpoint of the string is, and that guess cannot be made deterministically without reading the full string first
• C. Because the alphabet is too large for a deterministic PDA to track
• D. Because palindrome recognition requires a Turing machine and cannot be done by any PDA

Answer: (B)

To recognize {ww^R}, a PDA must push the first half of the string onto the stack and then match it against the reverse second half. The critical problem is identifying the midpoint — without seeing the full string, the machine cannot deterministically know when to switch from 'pushing' mode to 'matching' mode. A nondeterministic PDA can simply guess the midpoint nondeterministically and accept if any guess leads to a successful match. No deterministic PDA can solve this, which is why palindromes over non-unary alphabets are outside the deterministic context-free languages.

Question 2

Nondeterministic pushdown automata recognize exactly which class of languages?

• A. The regular languages — the same class as nondeterministic finite automata
• B. The decidable languages — all languages for which membership is decidable by a Turing machine
• C. The context-free languages — a strictly larger class than the regular languages
• D. The context-sensitive languages — one level above context-free in the Chomsky hierarchy

Answer: (C)

Nondeterministic PDAs recognize exactly the context-free languages — this is the central theorem connecting PDAs to context-free grammars (CFGs). Every language generated by a CFG can be recognized by an NPDA, and every language recognized by an NPDA can be generated by a CFG. Context-free languages strictly include the regular languages (all regular languages are context-free, but not vice versa), and context-sensitive languages strictly include the context-free languages.

Question 3

Just as most nondeterministic finite automaton can be converted to an equivalent deterministic finite automaton, nearly every nondeterministic pushdown automaton can be converted to an equivalent deterministic pushdown automaton.

• T. True
• F. False

Answer: False

This is a critical asymmetry compared to finite automata. For DFAs/NFAs, nondeterminism adds no power — the subset construction converts any NFA to an equivalent DFA. For PDAs, determinism strictly reduces power: deterministic PDAs (DPDAs) recognize a proper subset of the context-free languages. Languages like {ww^R} (palindromes) are context-free and recognized by NPDAs but not by any DPDA. This difference makes PDAs richer and more complex than finite automata in the nondeterminism dimension.

Question 4

A PDA can recognize {a^n b^n} (equal numbers of a's followed by b's) by pushing one stack symbol per 'a' read and popping one symbol per 'b' read, accepting when the stack is empty after consuming the full input.

• T. True
• F. False

Answer: True

This is the canonical example motivating PDAs. The PDA uses the stack as a counter: push a marker for each 'a', then pop one for each 'b'. If the stack empties exactly as the input is consumed, the counts matched. No DFA or NFA can do this because they have only finite memory and cannot count arbitrarily large n. The PDA's unbounded stack provides exactly the memory needed — illustrating why stacks are the right structure for counting matching pairs.

Question 5

Why can a finite automaton not recognize {a^n b^n}, and how does a pushdown automaton overcome this limitation?

Model answer: A finite automaton has a fixed, finite number of states. To recognize {a^n b^n}, the machine would need to remember the exact count of a's seen in order to verify the same count of b's follows. But any fixed number of states can only distinguish finitely many distinct counts — for sufficiently large n, the machine must revisit a state, losing track of the exact count. This is formalized by the pumping lemma for regular languages: {a^n b^n} can be pumped to produce words not in the language, proving no DFA accepts it. A PDA overcomes this by attaching an unbounded stack: push a marker for each 'a', pop one for each 'b'. The stack grows with n, providing exactly the unbounded counting memory that finite automata lack.

The stack gives the PDA a qualitatively different kind of memory: not a finite set of states but a LIFO structure that can grow without bound. This is the insight behind the hierarchy — regular → context-free → context-sensitive → recursively enumerable — each level has more memory: finite state, stack, linear-bounded tape, unbounded tape.