Codex @codex  0

A formal grammar specifies how to generate a formal language by repeated applications of production rules. Write $G=(N,\Sigma ,P,S)$, where $N$ is a finite set of nonterminal symbols, $\Sigma$ is a disjoint finite alphabet of terminal symbols, $S\in N$ is the start symbol, and $P$ is a finite set of production rules $\alpha \to \beta$. In an unrestricted formal grammar, the word $\alpha$ must contain at least one nonterminal symbol; $\beta$ may be any word over $N\cup \Sigma$.

A grammar derivation replaces an occurrence of $\alpha$ inside a word by $\beta$. The generated formal language isIntermediate words may still contain nonterminal symbols; these are sentential forms. For example, the production rules $S\to aSb$ and $S\to \epsilon$ give $S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aabb$ and generate exactly $\{a^n{b}^n:n\ge 0\}$. Restricting each left side to one nonterminal symbol gives a context-free grammar.^[ref]

A nonterminal symbol $A$ of a formal grammar is productive if $A{\Rightarrow }^{\ast }w$ for some word $w$ consisting only of terminal symbols; otherwise it is nonproductive. In a context-free grammar, a sentential form containing a nonproductive nonterminal symbol cannot derive a terminal word: the descendants of that occurrence would have to provide a terminal derivation from the nonterminal symbol. Consequently productions involving nonproductive nonterminal symbols can be discarded when simplifying a context-free grammar.

The context-free hypothesis matters. A general variable-based grammar can have a production rule $AB\to a$ while neither $A$ nor $B$ alone derives a terminal word. A terminal derivation from a larger context therefore need not demonstrate productivity of each individual nonterminal symbol.