GATE CSE 1999 | Question: 2.15

Question

A grammar that is both left and right recursive for a non-terminal, is

• A. Ambiguous

• B. Unambiguous

• C. Information is not sufficient to decide whether it is ambiguous or unambiguous

• D. None of the above

Comments

A grammar that is both left and right recursive for a non-terminal

I am saying a non-terminal(In given Question) is same as the same nonterminal(In my line) 
am I correct ??

 

 

---

1) Ambiguous grammar with left and right recursion on same terminal E

$$
E \rightarrow E + E \mid id
$$

This grammar is ambiguous, as the following string has 2 parse trees -

$$
id + id + id
$$

---

2) Un-ambiguous grammar with left and right recursion on same terminal E

$$
E \rightarrow aE \mid Ec \mid b
$$

This grammar is un-ambiguous as we don't have any choice in choosing the order of production to generate its' string. It has those strings in which we have all 'a' before a single 'b' and all 'c' after a single 'b'.

---

I agree with @Rajat_Singh. The answer should be A

Counter examples shown in Best Answer have useless productions. 

@divy.sisodia Your grammar 2 is still ambiguous :

Answer 1

Let grammar be like this :
$S \rightarrow a$
$A \rightarrow AbA$
This grammar is left as well as right recursive but still unambiguous. A is a useless production but still part of grammar..
A grammar having both left as well as right recursion may or may not be ambiguous.

---

---

Let's take a grammar say 

$S\rightarrow SS$

Now, according to the link https://en.wikipedia.org/wiki/Formal_grammar

For a grammar G, if we have L(G) then all the strings/sentences in this language can be produced after some finite number of steps .

But, for the grammar $$S\rightarrow SS$$

Can we produce any string after a finite number of steps? NO, and hence the language of this grammar is empty set {} .

Hence, If a grammar is having both left and right recursion, then grammar may or may not be ambiguous.

Correct Answer: $C$

Comments

@samarpita Sorry for the late reply.. I actually forgot to check… anyways… coming to your question… I guess, your thought process is correct. Assuming $\alpha$ and $\beta$ to be strings of terminals only [if $T$ represents the set of terminals then $\alpha \in T^*$ and $\beta \in T^*$]

Based on that I tried to think of a grammar as follows: [Note that I did not choose $S\rightarrow SS \mid \beta$ because it is provably ambiguous if you see]

Now the skeleton above which you said (or you were thinking of) is ambiguous for the type of strings shown in the drawing...

---

@samarpita HitechGa

1. A grammar having both left as well as right recursion
2. There will be no useless symbol

---- Then it will surely be ambiguous. 

Is it correct?

---

First Example is too good to analyze.

Answer 2

Information is insufficient ie C would be the correct option. 

Grammar that is both left recursive and right recursive can be ambiguous. 
Consider the grammar,

E -> E - E | T
T -> T / T | F
F -> num | ( E )

There can be 2 parse trees for "5-3-2"
1) one with correct associativity ((5-3)-2) 
2) one with wrong associativity (5-(3-2)).

So its clear that B can never be the correct option.

Source: http://pages.cs.wisc.edu/~fischer/cs536.s08/course.hold/html/NOTES/3.CFG.html#exp

Comments

But how this associativity can be directly connected with the representation of parse trees. You are applying associativity on the derived expression but the expression derived will be from the same parse tree isn't it?

Answer 3

Information is insufficient ie C would be the correct option. 

Grammar that is both left recursive and right recursive may or may not be ambiguous. 

example :

A → A a | b A | ε

(both left + right recursive but unambiguous)

Even though it has recursion on both sides, it can still be made to produce unique parse trees depending on the structure.

Comments

This Grammer is Ambigious 

---

Think this type of question different way it may ambigous and it may unambigous then we say  information is not sufficent

A-> B

B->a then it is unambigous right now think this direction also