In this exercise, we shall show that for every context-free language $L$ containing at least one string other than $\in,$there is a $CFG$ in Greibach normal form that generates $L-\in.$ Recall that a Greibach normal form $(GNF)$ grammar is one where every production body starts with a terminal. The construction will be done using a series of lemmas and constructions.
- Suppose that a CFG $G$ has a production $A\rightarrow\alpha B\beta,$ and all the productions for $B$ are $B\rightarrow \gamma_{1}|\gamma_{2}|....|\gamma_{n}.$Then if we replace $A\rightarrow\alpha B\beta$ by all the productions we get by substituting some body of a $B-$production for $B,$ that is $A\rightarrow\alpha\gamma_{1}\beta|\alpha\gamma_{2}\beta|....|\alpha\gamma_{n}\beta,$ the resulting grammar generates the same language as $G.$ In what follows,assume that the grammar $G$ for $L$ is in Chomsky Normal Form,and that the variables are called $A_{1},A_{2},....,A_{k}.$
- Show that by repeatedly using the transformation of part $(a),$ we can convert $G$ to an equivalent grammar in which every production body for $A_{i}$ either starts with a terminal or starts with $A_{j},$ for some $j\geq i.$ In either case, all symbols after the first in any production body are variables.
-
Suppose $G$ is the grammar that we get by performing step $(b)$ on $G.$ Suppose that $A_{i}$ is any variable and let $A\rightarrow A_{i}\alpha_{1}|....|A_{i}\alpha_{m}$ be all the $A_{i}$ productions that have a body beginning with $A_{i}.$ Let $A_{i}\rightarrow \beta_{1}|....|\beta_{p}$ be all the other $A_{i}-$ produtions. Note that each $B_{j}$ must start with either a terminal or a variable with index higher than $j.$ Introduce a new variable $B_{i},$ and replace the first group of $m$ productions by
$A_{i}\rightarrow\beta_{1}B_{i}|.....|\beta_{p}B_{i}$
$B_{i}\rightarrow \alpha_{1}B_{i}|\alpha_{1}|.....|\alpha_{m}B_{i}|\alpha_{m}$
Prove that the resulting grammar generates the same language as $G$ and $G_{1}.$
-
Let $G_{2}$ be the grammar that results from step $(c).$ Note that all the $A_{i}$ productions have bodies that begin with either a terminal or an $A_{j}$ for $j>i.$ Also all the $B_{i}$ productions have bodies that begin with either a terminal or some $A_{j}.$Prove that $G_{2}$ has an equivalent grammar in $GNF.$ Hint$:$ First fix the productions for $A_{k},$then $A_{k-1},$ and so on$,$ down to $A_{1}$ using part $(a).$ Then fi x the $B_{i}$ productions in any order , again $(a).$
