UGC NET CSE | September 2013 | Part 2 | Question: 16

Question

LL grammar for the language $L = \{a^n b^m c^{n+m} \mid m \geq 0, n \geq 0\}$ is

• A. $ S \rightarrow aSc \mid S_1 ; S_1 \rightarrow bS_1c \mid \lambda$
• B. $ S \rightarrow aSc \mid S_1 \lambda \mid S_1 \mid \lambda ; S_1 \rightarrow bS_1c $
• C. $ S \rightarrow aSc \mid S_1 \lambda \mid S_1 \mid \lambda ; S_1 \rightarrow bS_1c \mid \lambda$
• D. $ S \rightarrow aSc \mid S_1 \lambda ; S_1 \rightarrow bS_1c \mid \lambda$

Answer 1

Answer is C

in option A) n > 0 and m >0 in every condition so m=0 is not satisfied

in option B) There is no way to end the cycle S₁-> bS₁c

in option D) same condition as A

Comments

Why in option A) n > 0 in every condition so n =0 is not satisfied?

I can derive  S-> S1 ->bS1c->bλc =bc    //n=0

In same way n=0 will be in D also.

Moreover I think in C, we have S-> S1 and S-> S1λ both productions are starting with S1 , hence left recursive and ambiguous.

C cannot be the answer I think..

Please correct me if I am wrong.!

---

check for m = 0 in A and D

and S and S₁ different check it with pen and paper

---

can you give a example of a string for which we can eliminate option(A) and (D)

---

yeah, we can derive ac as well as bc in A.