Test by Bikram | Mock GATE | Test 2 | Question: 9

Question

Consider these three grammars.$$\begin{array}{|c|c|c|} \hline \textbf{Grammar G1:} & \textbf{Grammar G2:} & \textbf{Grammar G3:}  \\ \hline E\rightarrow E+T \mid T  & E\rightarrow E + T \mid T & E\rightarrow TR \mid R \\ \hline T\rightarrow T \ast v \mid v & T\rightarrow vR & R\rightarrow +T R \mid \varepsilon \\ \hline  & R\rightarrow \ast v R\mid\varepsilon & T\rightarrow T v\mid v   \\\hline\end{array}$$ 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 $G1$, then it can be generated by $G3$.
• C.      If $w$ can be generated by $G2$, then it can be generated by $G1$.
• D.      If w can be generated by $G3$, then it can be generated by $G1$.

Comments

@Neelesh v can be generated by G1 as well ...E->T->v

While G3 can generate +v which G1 cannot and so answer is D.

---

you can generate "epsilon" from G3 but you can not from G1

G3:   E->R  ....E->epsilon

---

@swagarika  @shiva  @Niharika1

please see my answer, explained it 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 | ε

Comments

B can not be true in G3 we don't have * and without this in G1 we cant produce v v v v v v

which is possible with G3

---

@Gate Fever 

it might be a printing mistake.

---

yes even i think , something wrong somewhere