CFG

Question

Why is S2 not a correct option?

Answer 1

Yes, S2 is not correct cause if the language generated by it is bound to contain $\in$ then we cannot remove that. Doing so will alter the language definition.

So S2 is false.

Comments

Could u give me some example of such grammer?

---

$L = \{\epsilon\}$, now there is no way we can write a CFG for $L$ without an $\epsilon$.

---

good luck reducing this grammar:
 

$$S \rightarrow \ \in$$

---

Yes even grammar wth S->epsilon ,no way eliminate epsilon

Answer 2

Suppose we have a Grammar 

S $\rightarrow$ bA

A $\rightarrow$ aA|∊

set of strings,language, generated is { b, ba, baa, baaa,....}

if we remove null from it ( following the rules) 

we will get

S$\rightarrow$bA|b

A$\rightarrow$aA|a

set of strings ,language, derived will be remains same. 

But if we have Grammar 

S$\rightarrow$aS|∊         , set of strings derived is {∊,a,aa,aaa,......}

and we remove null from it , we will get 

S$\rightarrow$aS|a        , set of strings derives is {a,aa,aaa,......}

languages will differ. 

Yes,for S2 only if we are not getting , null in language , directly ,S$\rightarrow$∊ , or indirectly, S$\rightarrow$A, A$\rightarrow$∊ (for example)

Comments

@Praveen Sir, before doing null production elimination we should make sure that our grammar should not generate null, otherwise it will give wrong grammar after null production elimination stage.

As in this example,

S→aS|∊      

After Null production elimination

S→→aS|a

which is wrong.

right??

---

Right :)