# Ullman (TOC) Edition 3 Exercise 7.3 Question 7 (Page No. 299)

22 views

Complete the proof of theorem $7.27$ by showing that

$(q_{P},w,Z_{0})\vdash(q,\in,\gamma)$ if and only if $(q_{P},q_{A},w,Z_{0}) \vdash((q,p),\in,\gamma),$  where $p =\hat{\delta}(p_{A},w).$

edited

## Related questions

1
27 views
Give the formal proof of theorem $7.25:$ that the $CFL's$ are closed under reversal.
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.