6,146 views

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).

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$.

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$

Since S--->C  and C--->d, you put S--->d. So shuldn't we delete the production C----d from the grammar??
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
Why can’t we replace C with d, and remove C->d as it’s a unit production too, right?

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

A------> aA / a

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

C-------> d

$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.

thats a typo :O
@arjun sir u also add A->aA , B->bB, C->d  then it will be fine ??
No, $S \to ABA$ cannot be there.
C->d is a unit production.

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

A -> aA | a

B -> bB | b
by

### 1 comment

How can C production be unit production

d is a terminal