# Ullman (TOC) Edition 3 Exercise 7.1 Question 9 (Page No. 278)

31 views

Provide the inductive proofs needed to complete the following theorems$:$

1. The part of Theorem $7.4$ where we show that discovered symbols really are generating.
2. Both directions of Theorem $7.6$ where we show the correctness of the algorithm in Section $7.1.2$ for detecting the reachable symbols.
3. The part of Theorem $7.11$ where we show that all pairs discovered really are unit pairs.

## Related questions

1
15 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. ... $,$ 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.
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.
Suppose $G$ is a CFG with $p$ productions, and no production body longer than $n.$Show that if $A\xrightarrow[G]{*}\in,$ then there is a derivation of $\in$ from $A$ of no more than $\frac{(n^{p}-1)}{(n-1)}$ steps. How close can you actually come to this bound$?$