search
Log In
0 votes
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).$

in Theory of Computation
retagged by
18 views

Please log in or register to answer this question.

Related questions

0 votes
0 answers
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.
asked Apr 11, 2019 in Theory of Computation Lakshman Patel RJIT 21 views
0 votes
0 answers
2
40 views
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.
asked Apr 11, 2019 in Theory of Computation Lakshman Patel RJIT 40 views
0 votes
0 answers
4
59 views
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.
asked Apr 11, 2019 in Theory of Computation Lakshman Patel RJIT 59 views
...