edited by
7,552 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

Best answer
55 votes
55 votes

Final grammar is

  • $S \rightarrow ABAC \mid ABC \mid BAC \mid BC \mid AC \mid AAC \mid d $
  • $A \rightarrow aA \mid a$
  • $B \rightarrow bB \mid b$
  • $C \rightarrow d $  
edited by
3 votes
3 votes
Answer should be

S-----> ABAC  / BAC /AAC/ABC/ABA/AC/BC/d

A------> aA / a

B-------> bB / b

C-------> d
–2 votes
–2 votes

S\rightarrow ABAC \mid BAC \mid AAC\mid ABC \mid ABA

A\rightarrow aA \mid a

B\rightarrow bB \mid b

C\rightarrow d

There are no unit productions.
–3 votes
–3 votes
C->d is a unit production.

so first production will become S -> ABAd | BAd | AAd | ABd | Bd | d

A -> aA | a

B -> bB | b

Related questions

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