made easy test

Question

1. ambiguous

2. left recursive

3. unambiguous

4. None

Answer 1

1. we  find  more than 1 parse tree for  string ab , so it is ambigious.
2. no left recursive . we dont have any A--A op B  kind of production so 2nd is wrong.
3. no , it is not un-ambigious
4.wrong
soln -A

Answer 2

The given grammar is ambiguous.Let us see how.

First of all it is not left recursive since for left recursion we must have production of type

S --> Sa directly or indirectly which is not the case here.

Consider drawing the derivation of a string say ab , so ambiguity comes as which of the 2  "A's" to be substituted first.Either of them can be done.To elaborate , we see reduction of "ab" in 2 ways , sufficient to show grammar is ambiguous.

S --> Aab --> ab [In case second A is substituted by epsilon]

S --> aAb --> ab [In case first A is substituted by epsilon]

So corresponding to these 2 reductions , we will get different derivation trees.Hence the grammar is ambiguous.

For more reference and clarity , u can check the following link where 

S -> aS | aSbS | epsilon is proved ambiguous on the similar ground :

https://cs.nyu.edu/courses/spring01/G22.2110-001/ans1.html

Hence A) should be the correct option.

Comments

thnx habib