edited by
7,551 views
34 votes
34 votes

Let $G$ be a context-free grammar where $G=(\{S, A, B, C\}, \{a, b, d\}, P, S)$ with the productions in $P$ given below.

  • $S \rightarrow ABAC$
  • $A \rightarrow aA \mid \varepsilon$
  • $B \rightarrow bB \mid \varepsilon$
  • $C \rightarrow d$

($\varepsilon$ denotes the null string). Transform the grammar $G$ to an equivalent context-free grammar $G'$ that has no $\varepsilon$ productions and no unit productions. (A unit production is of the form $x \rightarrow y$, and $x$ and $y$ are non terminals).

edited by

5 Answers

–4 votes
–4 votes

After removal of ∈-productions, 

S -> ABAC / BC / AAC / C

A -> aA

B -> bB

C -> d 

So, unit production = S -> C

After elimination of Unit production - 

S -> ABAC / BC / AAC / d

A -> aA

B -> bB

C -> d

Related questions

38 votes
38 votes
2 answers
8
Kathleen asked Oct 9, 2014
12,697 views
The pass numbers for each of the following activitiesobject code generationliterals added to literal tablelisting printedaddress resolution of local symbols that occur in...