The Gateway to Computer Science Excellence
0 votes

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

    $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 by Veteran (58.8k points)
retagged by | 7 views

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,291 answers
104,898 users