Context-free grammar

Remarks

Example: $N = \set{S}$, $\Sigma = \set{(, )}$, $P = \set{S \to SS, \ S \to (S), \ S \to \varepsilon}$. Every left side is the single nonterminal $S$, so this grammar is context-free; it generates the balanced strings of brackets. Non-example: a grammar with the rule $aA \to ab$ is not context-free, because the left side has two symbols. A leftmost derivation rewrites the leftmost nonterminal at each step. A derivation of a string $w$ corresponds to a parse tree, a rooted tree with root $S$. Its inner nodes are labelled by nonterminals, the children of a node are read off a rule, and the leaves spell $w$ from left to right. Parse trees of $w$ are in bijection with leftmost derivations of $w$.