Context-free grammars (CFG) — productions, derivations, parse trees: Visual walkthrough

Step 0 — The four things we start with

Before anything grows, we need to agree on our tools. A grammar has four parts. Let us name them with plain words first, then attach the fancy letters.

Our grammar for the whole page:

Figure — Context-free grammars (CFG) — productions, derivations, parse trees

Look at the picture: the blue box is the placeholder $S$ , the orange characters are the terminals it can turn into, and the red $ε$ is the eraser. That is our entire toolkit. Our goal for the walkthrough: build the string (()) — two brackets nested inside two brackets — and prove it belongs to this grammar.

Step 1 — The seed

WHAT. We begin, as every derivation must, with the start symbol alone: $S$

WHY. There is nothing else to begin with — $S$ is the only starting placeholder. Every legal string in this grammar must trace back to this single seed. If we cannot reach a string from $S$ , that string is not in the language.

PICTURE. Below, the tree is just one blue node. The tree will grow downward as we apply rules; the leaves read left-to-right will always spell our current string. Right now the only leaf is $S$ itself — an unfinished placeholder, so the string is not done.

Step 2 — First rewrite: open a bracket

WHAT. We apply the rule $S \to (S) S$ to our single $S$ : $S \Rightarrow (S) S$

The double arrow $\Rightarrow$ means "rewrites in one step" — read it as "becomes". (Contrast the single arrow $\to$ , which lives inside a rule; the double arrow $\Rightarrow$ is us using a rule.)

WHY. We want a bracketed string, so we must produce an actual open bracket $($ . The only rule that gives us brackets is $S \to (S) S$ . So we choose it.

PICTURE. In the tree, the old $S$ node sprouts four children, left to right: $(, S,), S$ . Two of those children ( $($ and $)$ , orange) are finished terminals — leaves that will never grow again. Two of them ( $S$ , blue) are still placeholders and will grow later.

$terminal, done (placeholder S terminal, done) placeholder S$

Step 3 — Kill the trailing placeholder

WHAT. Our current string is $(S) S$ . We now apply $S \to ε$ to the rightmost $S$ : $(S) S \Rightarrow (S)$

WHY. We want (()) — a single outer group with nothing after it. The trailing $S$ threatens to add more stuff on the right. To stop that, we erase it: $S \to ε$ turns it into nothing.

PICTURE. In the tree, the rightmost blue $S$ gets one child: a red $ε$ leaf. An $ε$ leaf contributes no character to the yield, so reading the leaves left-to-right now gives $(S)$ — the empty leaf simply disappears from the string.

Step 4 — Recurse inward: nest a second bracket

WHAT. Current string: $(S)$ . We apply $S \to (S) S$ again, this time to the inner $S$ : $(S) \Rightarrow ((S) S)$

WHY. We wanted (()), which has a second pair of brackets living inside the first. The only way to make more brackets is to expand a placeholder with $S \to (S) S$ once more. This is the moment recursion earns its keep: the same rule that opened the outer bracket now opens an inner one.

PICTURE. Look at the tree: the inner blue $S$ from Step 2 now sprouts its own four children $(, S,), S$ . We now have brackets inside brackets — the tree visibly grows a new layer. This nesting depth is exactly what a finite-state machine (a DFA) cannot count, and why we needed a grammar.

Step 5 — Erase the two remaining placeholders

WHAT. Current string: $((S) S)$ . Two blue placeholders remain. We erase both with $S \to ε$ : $((S) S) \Rightarrow (() S) \Rightarrow (())$

Wait — read carefully. After erasing the inner $S$ we have $(() S)$ ; after erasing the last $S$ we have $(())$ . Two clean-up moves.

WHY. Every remaining $S$ is an unfinished placeholder, and a string is only a finished word when no placeholders remain — when every leaf is a terminal. The nesting we wanted is already there; the leftover placeholders would only add clutter, so we switch them off.

PICTURE. Each remaining blue $S$ gets a red $ε$ child. The tree stops growing. Read the bottom leaves left to right, skipping the $ε$ 's: $($ $($ $)$ $)$ $=$ (()). Done.

Step 6 — Read the final answer

WHAT. No variable is left. The yield — the leaves read left-to-right — is $(())$ and every symbol in it is a terminal. Therefore $S \Rightarrow^{*} (())$ where $\Rightarrow^{*}$ means "rewrites in zero or more steps" — the whole chain we just walked, compressed into one claim.

WHY. Because we reached a string made only of terminals, starting from $S$ , this string is officially a member of the language: $(()) \in L (G_{1}), L (G_{1}) = {w \in Σ^{*} ∣ S \Rightarrow^{*} w} .$ Term by term: $Σ^{*}$ = "all strings over the terminal alphabet", the vertical bar $∣$ = "such that", and $S \Rightarrow^{*} w$ = "the seed can grow into $w$ ". So $L (G_{1})$ is the set of every string the seed can possibly become.

Step 7 — The degenerate case: building nothing

WHAT. What is the shortest possible member of this language? Apply the eraser immediately: $S \Rightarrow ε$

WHY. We must always check the boundary. The very first rule we may apply to the seed is $S \to ε$ , which finishes instantly with the empty string. So $ε \in L (G_{1})$ : the empty string of brackets is balanced (vacuously — nothing is unmatched).

PICTURE. The tiniest legal parse tree: a root $S$ with exactly one red $ε$ leaf. Zero brackets, and still perfectly valid. Every valid nesting story must be allowed to end, and this is that ending in its purest form.

The one-picture summary

Here is the whole walkthrough compressed: the seed at top, the string growing across five rewrites, and the finished parse tree whose leaves spell (()). The left-to-right yield of the leaves is the string — that is the single most important idea on this page.

Recall Feynman retelling — the whole story in plain words

Imagine one magic seed called $S$ . You have exactly two spells. Spell A turns a seed into: an open bracket, a new seed, a close bracket, and one more seed. Spell B makes a seed vanish. To build (()), you cast Spell A on the first seed to get a bracket pair with two baby seeds inside and after it. You vanish the after-seed (Spell B) so nothing trails. You cast Spell A on the inner seed to nest a second bracket pair. Then you vanish the last two seeds. When no seeds remain, you read off the brackets left to right: (()). The family tree of which seed split into which is the parse tree — and no matter what order you cast the vanish-spells, the family tree is the same. That sameness is why "more steps" never means "more structure".

Recall What does the double arrow

$\Rightarrow$ mean, and how is it different from $\to$ ? $\to$ appears inside a rule (a rewrite you're allowed to make). $\Rightarrow$ is you actually applying one such rule to the current string ("becomes in one step"). $\Rightarrow^{*}$ = zero or more such steps chained together.

Recall Why is

$ε \in L (G_{1})$ ? Because $S \Rightarrow ε$ in one step via the erase rule — the empty string is derivable from the seed, and it contains only terminals (namely, none), so it qualifies.

Recall Why can this grammar do something no DFA can?

Building (()) required opening a bracket, then recursing inside to open another. That unbounded nesting is unbounded counting, which a finite-state DFA cannot track — it needs the stack of a pushdown automaton.

Connections

Parent topic
Regular expressions and DFAs
Pushdown automata
Chomsky hierarchy
Chomsky normal form
Pumping lemma for CFLs
Compilers — parsing