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

This page assumes nothing. If you have never seen a set, an arrow, or a star before, start here and every symbol used in the parent topic will be earned before it appears.

0. The picture behind everything: letters vs. placeholders

Imagine two buckets of tokens on a table.

• The left bucket holds finished letters — things like (, ), a, +. Once one of these is placed, it never changes again. Call these terminals.
• The right bucket holds placeholders — labels like $S$, $E$, $T$. A placeholder is a promise: "something will go here later, but not yet." Call these variables (or non-terminals).

Every idea below is about the rules for turning right-bucket tokens into left-bucket tokens.

1. A set and the symbol $\in$

Why the topic needs it. The parent writes $A\in V$ and $S\in V$. These are just saying "$A$ is one of the placeholder tokens" and "$S$ is one of them too." No membership symbol, no way to say which tokens are legal.

The symbol $\varnothing$ means the empty set — a bag with nothing inside. The parent's rule $V\cap \Sigma =\varnothing$ (the two buckets share no token) uses it.

2. The alphabet $\Sigma$ and strings

Why $\Sigma$ and not just "letters"? We need a named, finite collection so a rule can say "your finished string may only use these characters." For matched parentheses, $\Sigma =\{(,)\}$ and nothing else.

3. The star $\ast$ (Kleene star) and ${\Sigma }^{\ast }$

Why this tool and not just "a string"? The parent needs to talk about every possible finished string at once — the language $L(G)$ is a subset of ${\Sigma }^{\ast }$. The star is the compact way to say "all strings over this alphabet, any length." We could not write $L(G)=\{w\in {\Sigma }^{\ast }\mid \dots \}$ without it.

The mixed version $(V\cup \Sigma {)}^{\ast }$ (used in the definition of a production) means "all strings you can build from placeholders AND letters mixed together" — because a half-finished line like $((S)S)$ contains both.

4. The empty string $\epsilon$

Why the topic needs it. The grammar $S\to (S)S\mid \epsilon$ relies on $\epsilon$ to end the recursion — without a rule that makes a placeholder disappear, you could never finish a string.

5. The arrow $\to$: a rewrite rule (production)

The pipe | is pure shorthand: $A\to {\alpha }_1\mid {\alpha }_2$ stacks two swap cards with the same left side onto one line.

6. The double arrow $\Rightarrow$: one derivation step

Why two different arrows? $\to$ is a rule that exists in your rulebook $R$. $\Rightarrow$ is an act of using one rule right now on your current line. One is potential, the other is an event.

7. The starred double arrow ${\Rightarrow }^{\ast }$: many steps

Why the topic needs it. The language is $L(G)=\{w\in {\Sigma }^{\ast }\mid S{\Rightarrow }^{\ast }w\}$: "all finished strings $w$ you can reach from the start placeholder $S$ by any number of swaps." Without ${\Rightarrow }^{\ast }$ you could only speak of one swap at a time and never define the full language.

8. The 4-tuple $G=(V,\Sigma ,R,S)$

Now every piece is earned, so the whole grammar-object makes sense:

9. Trees and yield (needed for parse trees)

Why the topic needs it. A derivation is a list of steps; a parse tree keeps only who-is-whose-child, discarding the order. You cannot understand "structure vs. order" or "ambiguity = two trees" without the tree picture first.

Prerequisite map

This map feeds directly into the parent CFG topic. It also connects forward to Pushdown automata (the machine that recognises what CFGs generate), Chomsky hierarchy (where CFGs sit), and Compilers — parsing (where parse trees get used). Contrast with Regular expressions and DFAs — the weaker tools that cannot count nesting.

Equipment checklist

Try to answer each before revealing: