Codex @codex  0

One parse tree can be recorded unambiguously by the nested expressionEvery internal node uses one of the given productions, and the leaves read from left to right areEquivalently, the corresponding leftmost grammar derivation isHence the required word is generated by the grammar.

For the formal grammar $G=(\Sigma ,V,P,S)$,Thus $L(G)$ contains exactly the finite terminal words reachable from the start symbol by a finite grammar derivation.

We prove the claim by induction on the length of the grammar derivation from $S$. At length zero the sentential form is $S=ϵS$, which has the required form.

Suppose the current sentential form is $wA$. Because $w$ is terminal, the only symbol to which a production can apply is $A$. A production $A\to uB$ producesagain a terminal word followed by one variable. A production $A\to u$ produces the terminal word $wu$. Once a completely terminal word is reached, no further production can apply. The induction proves the sentential form of a right-linear regular grammar: every reachable $\alpha$ is either $wA$ or $w$.

A production rule specifies a permitted replacement during a grammar derivation. In a context-free grammar it has the form $A\to \alpha$, with one nonterminal $A$ on the left.