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. ... $,$ down to $A_{1}$ using part $(a).$ Then fi x the $B_{i}$ productions in any order , again $(a).$

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.