A pushdown automaton recognizes a context-free language by reading a string and deciding accept or reject. A context-free grammar (CFG) instead generates the language: starting from a designated variable, it repeatedly rewrites variables into strings of variables and terminals according to production rules, until only terminal symbols remain. Every context-free language can be described by both a PDA and a CFG — they're two views of the same class of languages.

The formal definition

A CFG is a 4-tuple (V, Σ, R, S): a set of variables V, a set of terminals Σ, a set of production rules R of the form A → α (a variable rewrites to a string of variables and terminals), and a start variable S ∈ V.

Worked example: balanced parentheses

The language of correctly balanced parentheses — the same kind of structure the aⁿbⁿ PDA in the previous lesson recognizes — has a strikingly compact grammar:

S → ( S ) S
S → ε

Read the first rule as "a balanced string can be a balanced chunk wrapped in one pair of parens, followed by another balanced string," and the second as "the empty string is balanced." Deriving ()(): S → (S)S → ()S → ()(S)S → ()()S → ()(). Every derivation this grammar can produce is balanced, and every balanced string has some derivation — the two definitions of the language coincide.

From automaton to grammar, and back

The simulator can derive a skeleton CFG directly from a saved finite automaton: build or load an FA on the canvas, then use Create CFG from the hamburger menu. Each transition p --a--> q becomes a production P → a Q, and each accept state adds P → ε — a mechanical translation that works because every regular language is also context-free (finite automata are a strict subset of what PDAs, and therefore CFGs, can express).