Questions: Equivalence of CFGs and Pushdown Automata

Question 1

You want to prove that the language of well-formed HTML tags is context-free. You find a clean CFG that generates it, but constructing a PDA seems complicated. What does the CFG-PDA equivalence theorem allow you to conclude?

• A. You must construct both a CFG and a PDA — one alone is insufficient proof
• B. The CFG alone is sufficient proof — the equivalence theorem guarantees a PDA exists even if you don't build one
• C. A CFG can only prove a language is regular; PDAs are required for context-free proofs
• D. You should use the pumping lemma instead, since direct constructions are not rigorous proofs

Answer: (B)

The equivalence theorem states that CFGs and PDAs describe exactly the same class of languages. So if you have a CFG, you are guaranteed an equivalent PDA exists — and vice versa. Either construction is sufficient to prove a language is context-free. The power of the theorem is precisely this flexibility: choose whichever formalism makes your proof easier.

Question 2

Which statement best captures what the CFG-PDA equivalence theorem establishes?

• A. PDAs are strictly more powerful than CFGs because they have memory (the stack) that CFGs lack
• B. CFGs are more powerful for language specification; PDAs are more powerful for recognition — they complement each other
• C. CFGs and PDAs are equally expressive: the context-free languages are exactly the languages recognizable by PDAs
• D. PDAs can recognize all context-free languages, but CFGs can only generate a subset of them

Answer: (C)

The theorem establishes full equivalence — not complementarity or a power hierarchy. Every CFL can be generated by some CFG, and every CFL can be recognized by some PDA, and the two sets are identical. The CFG has no 'stack' in the traditional sense, but its recursive production rules achieve the same expressive power. Thinking of PDAs as 'stronger because they have memory' is the classic misconception the theorem refutes.

Question 3

The CFG-to-PDA construction is more complex than the PDA-to-CFG construction.

• T. True
• F. False

Answer: False

The CFG→PDA direction is the more intuitive one: the PDA simulates a leftmost derivation by pushing nonterminals and replacing them with production rule right-hand sides. The PDA→CFG direction is more mechanically involved, constructing nonterminals A_{pq} for each pair of states (p, q) and encoding transitions as production rules. The resulting grammar is often large and unwieldy, but proving its existence is what completes the equivalence.

Question 4

If a language can be recognized by a pushdown automaton, then some context-free grammar generates exactly that language.

• T. True
• F. False

Answer: True

This is the PDA→CFG direction of the equivalence theorem. For every PDA, there is an equivalent CFG that generates the same language. The construction creates nonterminals for each pair of states representing 'strings that move the PDA from state p to state q while returning the stack to its original height,' and production rules encode the transitions. The grammar may be large, but its existence proves the equivalence.

Question 5

Explain the key idea behind the CFG-to-PDA construction: what is the PDA doing with its stack, and how does this simulate the grammar?

Model answer: The PDA simulates a leftmost derivation of the CFG. It begins by pushing the start symbol onto the stack. At each step: if the top of the stack is a nonterminal, the PDA nondeterministically replaces it with the right-hand side of one of that nonterminal's production rules (pushing the symbols in reverse order so the leftmost symbol ends up on top). If the top is a terminal matching the next input character, the PDA pops it and advances. The PDA accepts when the stack is empty and all input is consumed — meaning it successfully derived the input string from the start symbol.

The stack tracks 'what remains to be derived.' At every point in the computation, the stack contains the suffix of a sentential form — the part of the derivation not yet matched against input. Nondeterminism is key: the PDA guesses which production rule to apply at each step, so there exists a computation path that accepts if and only if the input string is in the language.