CFG-PDA equivalence

This is the headline theorem of the field, the pushdown counterpart of 'regular expressions equal finite automata'. A language is generated by some context-free grammar if and only if it is recognised by some pushdown automaton. In one sentence: pushdown automata recognise EXACTLY the context-free languages — no fewer, no more. The generating view (grammars) and the recognising view (machines) describe the very same class.

Both directions are proved by explicit construction. From a grammar to a PDA: build a one-state PDA that accepts by empty stack and uses its stack to simulate a LEFTMOST derivation. It starts with the start symbol on the stack; whenever a variable is on top, it nondeterministically pops it and pushes the right-hand side of one of that variable's rules (guessing which rule to apply); whenever a terminal is on top, it pops it only if it matches the next input symbol. If the input exactly matches some derivation, the guesses line up, the stack empties, and the machine accepts. From a PDA back to a grammar is the harder direction: you introduce variables that stand for 'the machine goes from state p to state q while net-popping a particular stack symbol', and the rules are built to mirror the PDA's moves; the resulting grammar generates exactly the PDA's language.

The payoff is that you can move freely between the two pictures depending on which is easier. Want to PROVE a language is context-free? Either give a grammar or give a PDA — both suffice. Want to PARSE? Grammars are how you specify a language, PDAs (and their deterministic restriction) are how you recognise it efficiently. This equivalence is exactly the rung of the Chomsky hierarchy that sits one step above the regular languages, and it is why the stack is the defining resource of context-free power.