A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
A language is context-free if and only if it is recognized by some pushdown automaton. This equivalence is established by converting CFGs to PDAs and PDAs to CFGs. It demonstrates that context-free grammars and pushdown automata are equally expressive computational models.
From your work with pushdown automata, you know that a PDA is a finite automaton augmented with a stack — and that this stack gives it the power to recognize languages like {aⁿbⁿ} that no DFA or NFA can handle. You also know that context-free grammars generate languages through production rules and derivations. The fundamental theorem here is that these two formalisms — one a machine model, the other a generative grammar — describe exactly the same class of languages. Every CFG has an equivalent PDA, and every PDA has an equivalent CFG.
The direction from CFG to PDA is the more intuitive one. The idea is to build a PDA that simulates a leftmost derivation of the grammar. The PDA starts 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 its productions (pushing the symbols in reverse order so the leftmost one ends up on top). If the top of the stack is a terminal that matches the next input character, the PDA pops it and advances. If the stack empties after all input is consumed, the string is accepted. In effect, the PDA is "guessing" a derivation and checking it against the input, using the stack to track what still needs to be matched.
The reverse direction — PDA to CFG — is more involved. The construction creates a nonterminal A_{pq} for each pair of states (p, q), representing "strings that take the PDA from state p with some stack symbol pushed to state q with that symbol popped." The production rules encode the PDA's transitions: if the PDA can push a symbol in state p and eventually pop it in state q, passing through intermediate states, the grammar captures that path. The resulting grammar is often large and unwieldy, but its existence is what matters — it proves that any language a PDA can recognize, a CFG can generate.
Why does this equivalence matter? It gives you two complementary ways to reason about context-free languages. Grammars are convenient for specifying syntax — every programming language's parser is built from a grammar. Automata are convenient for proving properties about what can and cannot be recognized. When you need to show that a language is context-free, you can build whichever model is easier: sometimes a grammar is obvious, sometimes a PDA is more natural. The equivalence guarantees that either proof suffices. This mirrors the DFA/NFA/regex equivalence for regular languages — and the same principle recurs throughout theory of computation: different formalisms at the same level of power give you different tools for the same class of problems.