Context-Free Grammars and Normal Forms

Suppose first that $S{\Rightarrow }_G^{\ast }w$. Start with one root labelled $S$ and process the derivation step by step. When a step rewrites a current leaf labelled $A$ by a nonempty right-hand side $x_1\cdots x_k$, make that leaf an internal node with ordered children labelled $x_1,\dots ,x_k$. When a step uses $A\to \epsilon$, leave that leaf in place as the variable leaf corresponding to the $\epsilon$-production. Because the derivation is finite, this constructs a finite parse tree whose nodes record exactly the productions used in the derivation.

Conversely, suppose a parse tree for $G$ has yield $w$. Start from the sentential form $S$ and repeatedly rewrite the leftmost variable leaf represented in the fixed tree: if that leaf is an internal node of the tree with ordered children $x_1,\dots ,x_k$, apply the production $A\to x_1\cdots x_k$; if it is a variable leaf corresponding to $A\to \epsilon$, apply that $\epsilon$-production. By [L2], every step is licensed by $G$, and by construction every step is leftmost in the sense of [L1]. Because the tree is finite, this process terminates after one step for each variable-labelled node, and the final terminal frontier is exactly the yield $w$.

At the end of the construction in step 1.1, the leaves read left to right are exactly the symbols of the terminal word $w$, because each derivation step replaces one leaf occurrence of $A$ by the same ordered right-hand side that the tree stores. So a derivation of $w$ yields a parse tree whose yield is $w$.

The choice in step 1.2 is forced: at each stage there is a unique leftmost variable leaf of the fixed parse tree, so the leftmost derivation read from the tree is unique. The same argument, reading rightmost variable leaves instead, gives a unique rightmost derivation.

Steps 1.1 and 2.1 prove the forward implication of clause 1, and step 1.2 proves the reverse implication. Step 2.2 proves clause 2.

Let $T\subseteq V$ be the generating variables of $G$, and let $P_1$ consist of the productions whose left-hand side lies in $T$ and whose right-hand side contains no variable outside $T$. If $S\mathrm{\notin }T$, then no terminal word is derivable from $S$, so [L2] gives $L(G)=\mathrm{\varnothing }$ and we may take $G^{\mathrm{\prime }}$ to be any fixed grammar generating the empty language. If $S\in T$, set $G_1:=(T,\mathrm{\Sigma },P_1,S)$.

In the case $S\in T$, let $R\subseteq T$ be the variables reachable from $S$ in $G_1$, let $P_2$ consist of the productions in $P_1$ whose left-hand side lies in $R$ and whose right-hand side contains no variable outside $R$, and set $G_2:=(R,\mathrm{\Sigma },P_2,S)$. Every derivation beginning at $S$ stays inside $R$ by definition of reachability.

Assume now that $S\in T$. Any derivation of a terminal word can use only generating variables, because every variable appearing in that derivation must eventually derive a terminal subword. Conversely, every rule kept in $G_1$ was already a rule of $G$. Hence $L(G_1)=L(G)$.

Therefore deleting the unreachable variables changes no derivation from $S$ to a terminal word, while every variable remaining in $G_2$ is both generating and reachable. So $L(G_2)=L(G_1)=L(G)$.

Taking $G^{\mathrm{\prime }}=G_2$ in the case $S\in T$ and the empty-language grammar in the case $S\mathrm{\notin }T$ proves the theorem.

Let $N$ be the nullable variables of $G$. Form a grammar $G_{\epsilon }$ by deleting every production $A\to \epsilon$ and, for each remaining production $A\to x_1\cdots x_k$, adding every nonempty right-hand side obtained by deleting any chosen subset of nullable occurrences among the $x_i$.

If $\epsilon \mathrm{\notin }L(G)$, clause 1 already proves the theorem. Assume instead that $\epsilon \in L(G)$. Introduce a fresh start variable $S_0$ and add the two productions $S_0\to S$ and $S_0\to \epsilon$, leaving all productions of $G_{\epsilon }$ unchanged.

Any derivation of a nonempty terminal word in $G$ can be shortened to one in $G_{\epsilon }$ by collapsing each maximal family of nullable subderivations into a single use of one of the added productions. Conversely, every added production in $G_{\epsilon }$ can be expanded back in $G$ by re-inserting derivations of the deleted nullable variables to $\epsilon$. Therefore [L2] gives $L(G_{\epsilon })=L(G)\setminus \{\epsilon \}$.

The rule $S_0\to \epsilon$ restores the missing empty word, while step 2.1 already preserved every nonempty terminal word. Because $S_0$ is fresh, it appears on no right-hand side, so this is the only $\epsilon$-production of the new grammar $G^{\mathrm{\prime }}$. Hence $L(G^{\mathrm{\prime }})=L(G)$.

Replace $G$ by an equivalent grammar $G_1$ as in [L1]. For variables $A,B$, write $A⇝B$ when $A{\Rightarrow }_{G_1}^{\ast }B$ using only unit productions. Now form $H$ by deleting all unit productions and, whenever $A⇝B$ and $B\to \alpha$ is a nonunit production of $G_1$, adding the copied production $A\to \alpha$.

Any derivation of a terminal word in $G_1$ can be compressed to a derivation in $H$ by replacing each maximal block of unit productions followed by one nonunit production $B\to \alpha$ with the copied rule $A\to \alpha$ placed into $H$. Therefore every word of $L(G_1)$ lies in $L(H)$.

Conversely, every copied production $A\to \alpha$ of $H$ came from some unit chain $A⇝B$ in $G_1$ and a nonunit production $B\to \alpha$ of $G_1$. Expanding one use of $A\to \alpha$ back into that unit chain followed by $B\to \alpha$ turns any derivation in $H$ into a derivation in $G_1$. So every word of $L(H)$ lies in $L(G_1)$.

Steps 2.1 and 2.2 give $L(H)=L(G_1)=L(G)$, and $H$ has no unit productions by construction.

Apply [L1], [L2], and [L3] in order to obtain an equivalent grammar $G_1$ in which every remaining production is nonunit and every $\epsilon$-production is removed except possibly a start-symbol rule.

For each terminal $a$ that appears in a right-hand side of length at least $2$, introduce a fresh variable $T_a$ with production $T_a\to a$, and replace that occurrence of $a$ by $T_a$. This changes no generated word, because each use of $T_a$ can immediately be expanded to the terminal $a$. After this step, every right-hand side is either a single terminal or a word of variables only.

For each production $A\to B_1{B}_2\cdots B_k$ with $k\ge 3$, introduce fresh variables $C_1,\dots ,C_{k-2}$ and replace the production by $A\to B_1{C}_1,C_i\to B_{i+1}{C}_{i+1}(1\le i\le k-3),C_{k-2}\to B_{k-1}{B}_k\mathrm{.}$ The middle family is empty when $k=3$, so that case is the two-rule chain $A\to B_1{C}_1$ and $C_1\to B_2{B}_3$. One use of the original long rule is equivalent to this forced chain of binary rules, and conversely the binary chain produces exactly the same string of variables.

After steps 2.1 and 3.1, every production is either $A\to BC$, $A\to a$, or the exceptional start-symbol rule $S\to \epsilon$. Therefore [L4] says the resulting grammar is in Chomsky normal form, and the preceding steps preserved the language.

Let $xAy{\Rightarrow }_{G}xuBvy$ be one use of the deleted production in a derivation of a terminal word, and follow the distinguished occurrence of $B$ created by this step. It is eventually rewritten by some $B\to w_i$, since the displayed rules are all the productions of $B$. Every intervening step rewrites a different variable occurrence. Such a step commutes with the rewrite of the distinguished $B$: applying the two context-free productions in either order gives the same sentential form. We may therefore move $B\to w_i$ leftward past all intervening steps and replace the resulting adjacent fragment $xAy{\Rightarrow }_{G}xuBvy{\Rightarrow }_{G}xu{w}_{i}vy$ by the single $H$-step $xAy{\Rightarrow }_{H}xu{w}_{i}vy$. Restoring the commuted surrounding-context steps gives the same final terminal word.

Conversely, every use in $H$ of a substituted production $A\to u{w}_{i}v$ can be expanded in $G$ to the two steps $xAy{\Rightarrow }_{G}xuBvy{\Rightarrow }_{G}xu{w}_{i}vy\mathrm{.}$ Replacing each substituted step in a derivation of a terminal word in $H$ by this two-step fragment yields a derivation in $G$ with the same yield. Hence [L2] gives $L(H)\subseteq L(G)$.

If a terminal derivation in $G$ never uses the deleted production $A\to uBv$, then it is also a derivation in $H$. Otherwise apply step 1.1 to one use of $A\to uBv$. This decreases by one the number of uses of the deleted production in the finite derivation without changing its terminal yield. Repeating finitely many times produces an $H$-derivation of the same word, so [L2] gives $L(G)\subseteq L(H)$.

The two inclusions from steps 2.1 and 1.2 prove $L(H)=L(G)$.

Consider a leftmost derivation segment in the original grammar beginning with $A$. Because every left-recursive rule has the form $A\to A{u}_i$, any maximal initial block of left-recursive steps must look like $A\Rightarrow A{u}_{i_1}\Rightarrow A{u}_{i_2}{u}_{i_1}\Rightarrow \cdots \Rightarrow A{u}_{i_k}\cdots u_{i_1}\Rightarrow v_j{u}_{i_k}\cdots u_{i_1}\mathrm{.}$ So the contribution of this segment is always one non-left-recursive word $v_j$ followed by a finite concatenation of the $u_i$.

The new variable $R$ generates exactly the nonempty finite concatenations of the $u_i$: use $R\to u_i$ for a one-term concatenation and $R\to u_{i}R$ to prepend further $u_i$'s. Therefore the segment in step 1.1 is reproduced in the rewritten grammar either by $A\to v_j$ when $k=0$ or by $A\to v_{j}R$ followed by a derivation of the same tail from $R$ when $k\ge 1$.

Conversely, any derivation segment in the rewritten grammar beginning with $A$ either uses $A\to v_j$ directly or uses $A\to v_{j}R$ followed by a derivation of a finite concatenation of the $u_i$ from $R$. Reversing the regrouping in step 1.1 turns that segment back into a block of left-recursive uses of $A\to A{u}_i$ ending with $A\to v_j$ in the original grammar.

Since all other productions are unchanged, steps 2.1 and 3.1 convert derivations of terminal words back and forth without changing the yield. Hence [L2] gives equality of the generated languages.

Replace $G$ by an equivalent CNF grammar $G_1$ as in [L1], and order its original variables as $A_1,\dots ,A_n$. In a forward pass through this list, fix $A_i$ and repeatedly use [L2] to remove every production of the form $A_i\to A_j\alpha$ with $j<i$. When that is done, use [L3] to eliminate the remaining immediate left-recursive productions $A_i\to A_i\beta$, introducing an auxiliary variable $B_i$ if needed. After stage $i$, every production of $A_i$ begins either with a terminal or with an original variable $A_k$ satisfying $k>i$, and every new production of $B_i$ begins either with a terminal or with an original variable.

In particular, after the forward pass the productions of $A_n$ already begin with terminals, because there is no index $k>n$. Now argue downward on $i=n-1,n-2,\dots ,1$. Assume the productions of $A_{i+1},\dots ,A_n$ already begin with terminals. Every production of $A_i$ begins either with a terminal or with some $A_k$ having $k>i$ by step 1.1, so repeated use of [L2] substitutes the full terminal-leading production family of each such $A_k$ into the leading occurrence. Thus every production of $A_i$ can also be made terminal-leading without changing the language.

The same downward substitutions clean every auxiliary variable introduced during the left-recursion eliminations. By step 1.1, each production of such a $B_i$ already begins either with a terminal or with an original variable $A_k$. Once the productions of each $A_k$ are terminal-leading by step 2.1, repeated use of [L2] removes that leading variable from the productions of $B_i$ as well. Therefore, after finitely many substitutions, every production in the whole grammar begins with a terminal, except possibly the start-symbol rule $S\to \epsilon$.

Because the construction started from CNF, the symbols after the first terminal in any rewritten production are variables, and the optional start-symbol rule $S\to \epsilon$ is preserved only in the exceptional case allowed by [L4]. Hence the final grammar is in Greibach normal form, and [L2] and [L3] preserved equivalence throughout.

Rename variables of $G_1$ and $G_2$ apart, and add a fresh start variable $S$. The grammar with productions of $G_1$ and $G_2$ together with $S\to S_1$ and $S\to S_2$ generates exactly $L_1\cup L_2$. Similarly, adding only the bridge rule $S\to S_1{S}_2$ yields a grammar for the concatenation $L_1{L}_2$.

For Kleene star, keep $G_1$ and add a fresh start variable $S$ with productions $S\to \epsilon$ and $S\to S_{1}S$. Repeating the second rule any finite number of times and then using $S\to \epsilon$ generates exactly a concatenation of finitely many words from $L_1$, so the new grammar generates $L_1^{\ast }$.

For homomorphism, first rename the variables of the chosen grammar for $L_1$ so that they are disjoint from $\mathrm{\Delta }$. Then replace every terminal letter $a$ occurring in a production by the word $h(a)$, keeping that renamed variable set unchanged. The result is still a context-free grammar over $\mathrm{\Delta }$, and if a derivation in the source grammar yields $w=a_0\cdots a_{n-1}$, then the corresponding derivation in the rewritten grammar yields $h(a_0)\cdots h(a_{n-1})=\widehat{h}(w)$ by [L2].

Conversely, any terminal derivation in the rewritten grammar follows the same variable-expansion pattern as a terminal derivation in the renamed source grammar, because the only change was to replace each source terminal occurrence by its prescribed image word $h(a)$. Therefore the terminal word produced at the end is exactly the image under $\widehat{h}$ of a word of $L_1$, so the new grammar generates exactly $\widehat{h}(L_1)$.

Steps 1.1, 1.2, 1.3, and 2.1 construct grammars for all four languages, so [L1] shows that context-free languages are closed under union, concatenation, Kleene star, and homomorphism.

The displayed grammar is ambiguous: the word $a+a\ast a$ has one parse corresponding to $a+(a\ast a)$ and another corresponding to $(a+a)\ast a$. So the grammar is an ambiguous CFG.

The standard precedence grammar $E\to E+T\mid T,T\to T\ast F\mid F,F\to (E)\mid a\mid b$ generates the same terminal strings. One inclusion follows by simultaneous induction on its $E$-, $T$-, and $F$-derivations, since every displayed production can be simulated by the first grammar. For the reverse inclusion, scan a generated word at parenthesis depth zero: if there is a +, split at the rightmost such +; otherwise, if there is a *, split at the rightmost such *; the remaining factor is either $a$, $b$, or a parenthesized expression. Induction on the word length gives a derivation in the precedence grammar. These rightmost top-level splits are forced by its left-recursive $E$- and $T$-rules, while the $F$-case is forced by the outer symbols, so the resulting parse is unique. In particular, $a+a\ast a$ has only the parse $a+(a\ast a)$. Thus the language has an unambiguous grammar.

By [L1], a language with an unambiguous grammar is not inherently ambiguous. So the ambiguous grammar from step 1.1 does not force its language to be inherently ambiguous, and [A1] is false.

The given grammar generates exactly the language $\{\epsilon \}$. So any equivalent CNF grammar must still generate $\epsilon$.

Without the exception described in [L1], every CNF production would have the form $A\to BC$ or $A\to a$. Such rules can produce only nonempty terminal words, because every terminal step contributes one symbol and no rule deletes all remaining symbols. Therefore a grammar with only those two rule types cannot generate $\epsilon$.

Step 1.2 contradicts the requirement from step 1.1, so the special start-symbol exception is genuinely necessary. The claim [A1] is false.