GATE CSE 2001 | Question: 18

Question

• A. Remove left-recursion from the following grammar: $S \rightarrow Sa \mid Sb \mid a \mid b$
• B. Consider the following grammar: 

             $S \rightarrow aSbS\mid bSaS \mid \epsilon$

             Construct all possible parse trees for the string abab. Is the grammar ambiguous?

Comments

The grammar in A is making Language : (a+b)+ positive closure

 

Answer 1

1. $S \rightarrow aS'\mid bS'$
   $S' \rightarrow aS' \mid bS' \mid \epsilon$
    
2. $S \rightarrow aSbS \rightarrow abS \rightarrow abaSbS \rightarrow ababS \rightarrow abab$
   $S \rightarrow aSbS \rightarrow abSaSbS \rightarrow abaSbS \rightarrow ababS \rightarrow abab$ 

The above two derivations corresponds to two different parse trees and hence the grammar is ambiguous.

Comments

Two derivation so it is ambiguous

Gammer is ambiguous. But above statement requires 

Refer --> Option(A) for https://gateoverflow.in/711/gate2001-1-18

ping @kenzou

---

@Chhotu, its edited now.

---

Or the answer can be simplified as:

S$\rightarrow$aS|bS|a|b

Answer 2

Remove left-recursion from the following grammar:

a) 

so by the basic rule==>

b)

left side parsing: S->aSbS->abS->abaSbS>ababS->abab

right side parsing:S->aSbS->abSaSbS->abaSbS->ababS->abab so it is ambiguous
 

Comments

I'm not able to see what's written here.

Is it just me ?  

---

TURN OFF THE DARK MODE

Answer 3

Grammar is Ambiguous