# Ullman (TOC) Edition 3 Exercise 7.1 Question 11 (Page No. 278 - 279)

18 views

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.

1. 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}.$
2. 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.
3. 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}.$

4. 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).$

retagged

## Related questions

1
21 views
Is it possible to find, for every context-free language without $\in,$ a grammar such that all its productions are either of the form $A\rightarrow BCD$ $($i.e., a body consisting of three variables$),$ or $A\rightarrow a$ $($i.e., a body consisting of a single terminal$)?$ Give either a proof or a counterexample.
Provide the inductive proofs needed to complete the following theorems$:$ The part of Theorem $7.4$ where we show that discovered symbols really are generating. Both directions of Theorem $7.6$ where we show the correctness of the algorithm in Section $7.1.2$ for detecting the reachable symbols. The part of Theorem $7.11$ where we show that all pairs discovered really are unit pairs.
Use the construction of question $11$ to convert the grammar $S\rightarrow AA|0$ $A\rightarrow SS|1$ to $GNF.$
Let $G$ be an $\in-$production-free grammar whose total length of production bodies is $n.$ We convert $G$ to $CNF.$ Show that the CNF grammar has at most $O(n^{2})$ productions. Show that it is possible for the $CNF$ grammar to have a number of productions proportional to $n^{2}.$ Hint$:$Consider the construction that eliminates unit productions.