MadeEasy Test Series 2018: Compiler Design - Left Recursion

Question

I think the answer should be option: C but it is given option A.

Providing the snapshot of the question with the options provided.

I don't think option A should be the correct one, even if it then we cannot derive string "bda" from option A which is possible in the original grammar.

Please help with this question.

Thanks in advance.

Comments

1. S->Ab|b
2. A-> A' |bdA'
3. A'->cA' |adA' |null

d is correct.

---

why not c

---

A-> A'  is missing since original grammar generate a but option c is not generate.

---

ok...could you help me in this question https://gateoverflow.in/163697/self-doubt

---

shivi 

1. A'->cA' |adA' |null should be there but it is given  A->cA' |adA' |null. so from where you use A'

---

Ya anu I  didn't notice that it was A not A'  my bad... thanks...

---

option A is wrong because second prod should be

A $\rightarrow$ bd${A}'$/${A}'$

---

Thanks @Mk Utkarsh so option C is the correct one right ?

---

it seems correct to me.

---

Option C shouldn't be the answer as well. In the third derivation ${A}'$ should be there on LHS and not A.

---

vishal chugh i'm not very good with this topic but help me pointing out any string that is not generated by C or any extra string by option C is generated as compared with given grammar

and i agree with you that's why i mentioned what's wrong with option A

---

Mk Utkarsh Its not a correct grammar only as ${A}'$ can't be evaluated. So I think they just did a typo in the LHS of last production. 

---

no opion is correct...because in c A' doesn't have terminalll....and

option a is not generating. ,....bda

---

yeah there is a typo in A option that's it

---

@vishal  I think the last production they made a type there, otherwise it would have been option C.

So, for this none of the production given in the option seems correct.

Thanks as I wanted to know how they have provided option A as the correct answer as its no way seems correct answer.

Thanks

---

Grammar after removing left recursion:

$S \rightarrow Aa|b$

$A \rightarrow bdA'|A'$

$A' \rightarrow cA'|adA'| \epsilon $

In option a) only error is $bA'$ in place of $bdA'$

---

none of the option is correct. i am really frustrated by seeing so many wrong questions in madeeasy test series.

---

agreed

---

"ca" is not being generated by option C but the actual grammer generates it

Answer 1

Ans is

S->Ab|b

A-> A' |bdA'

A'->cA' |adA' |null

Ans D is correct

Answer 2

S -> Aa/b

A -> Ac/Aad/bd/epsilon

there is left recursion for A production so remove it

A -> bdA'/A'       ------------ here A' for epsilon production as A ->epsilon  from the given production

A' -> cA'/adA'/epsilon

hence option (a) is correct

Comments

Option (A) is wrong here, it should be $A’\rightarrow bdA’/A’$

None of the given options is correct.

Answer 3

Your answer is correct,

The solution provided is wrong.

In the original grammar, we can generate $bda$

by using $S \rightarrow Aa$ and $A \rightarrow bd$, which will give bda

however, in the solution grammar provided, there is no way to generate $bda$

as there is no way to get $A \rightarrow bd$.

Answer 4

option B is correct 

option A can’t generate  bda

option C cant generate  cca