in Compiler Design edited by
6,146 views
32 votes
32 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).

in Compiler Design edited by
6.1k views

2 Comments

The numerical question that could be asked for this question is the number of productions after removing unit productions and $\epsilon$ productions.

For removing $\epsilon$ productions, first, check all the nullable variables. By nullable variables I mean the variables which can lead you to $\epsilon$.

So, in this question Nullable_Variables = $\{A,B\}$

Now in every production on the RHS, write those productions WITH and WITHOUT Nullable variables (all possible combinations).

For making sure you don’t miss any case, you can follow this method – 

$S \to ABAC$

$ABAC$

$000C = C$

$001C = AC$

$010C = BC$

$011C = BAC$

$100C = AC$

$101C = AAC$

$110C = ABC$

$111C = ABAC$

See that $AC$ is repeated so skip the repeated one in final answer.

For removing unit productions simply replace $S \to C$ with $S \to d$.

8
8
0
0

5 Answers

52 votes
52 votes
Best answer

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

4 Comments

Since S--->C  and C--->d, you put S--->d. So shuldn't we delete the production C----d from the grammar??
2
2
In question a unit production is of the form x->y WHERE X AND Y ARE NON TERMINAL . C-> d is not unit production.

But S->C is unit production
1
1
Why can’t we replace C with d, and remove C->d as it’s a unit production too, right?

Please help.
0
0
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.

4 Comments

thats a typo :O
1
1
@arjun sir u also add A->aA , B->bB, C->d  then it will be fine ??
0
0
No, $S \to ABA$ cannot be there.
1
1
–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

1 comment

How can C production be unit production

d is a terminal
3
3

Related questions