GateBook Mock Test_2(Compilers)

Question

Consider these three grammars.

Which of the following statements is not true?

(A) If w can be generated by G1, then it can be generated by G2.

(B) If w can be generated by G2, then it can be generated by G3.

(C) If w can be generated by G3, then it can be generated by G1.

(D) If w can be generated by G2, then it can be generated by G1.

Comments

But G1 & G2 genrate E+v  but G3 not so why not B also correct, B& C both should be the answer

---

G1 and G2 are actually the same. When we elliminate left recursion in T production from G1, We get G2.

---

@Rinky

No, C is the only answer, please check my answer below ..

Answer 1

In G1, T can take the form of v * v * v * v * v ....

In G2, R can take the form * v * v * v ...,  

so T can take the form of v * v * v * v ....

Thus, in both G1 and G2, E can take the form v * v * v + v * v * v * v + v * v ....

These are the algebraic expressions involving only addition and multiplication.

In G3, T can take the form v * v * v * v, so R can take the form + v * v + v * v. Thus, through the production E ! T R, E can take the form of any arithmetic expression.

However, E can also take the form of non-arithmetic expressions,

as with E --> R --> + T R --> + v R --> + v + T R ---> + v + v R --> + v + v.

In addition, G3 can generate ε , which G1 and G2 cannot.

Thus, while G1 and G2 generate the same language,

G3 generates a somewhat larger language. Incidentally, G1 demonstrates left-recursion because it contains productions of the form X --> X  α ( in addition to non-problematic productions of the form   X --> β ).

Left recursion can be eliminated by introducing a helper non-terminal R and changing the grammar to read

X --> β R
R --> α R | ε

hence C is the answer .

Comments

In G3 we can derive  ε also bt in G1 we can't derive  ε .
i think A is correct .