GATE CSE 1996 | Question: 11

Question

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

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

---

jatinmittal199510 nice 

Answer 1

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 $  

Comments

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?

Please help.

---

The given answer is correct. It’s mentioned in the question:-

A unit production is of the form $x→y$, and $x$ and $y$ are non terminals

Hence, $C→d$ can remain in the Grammar.

Answer 2

Answer should be

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

A------> aA / a

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

C-------> d

Answer 3

There are no unit productions.

Comments

S-> ABAC | BAC | AAC | ABC | BC | d

rt?

---

how to interpret this:

 

B->bB-> epsilon

---

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.

Answer 4

C->d is a unit production.

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

A -> aA | a

B -> bB | b

Comments

How can C production be unit production

d is a terminal