UGC NET CSE | June 2014 | Part 3 | Question: 73

Question

Given the following two grammars :

$G_{1} : S \rightarrow AB | aaB$

              $ A \rightarrow a | Aa$

              $B \rightarrow b$ 

$G_{2} : S \rightarrow a S b S | b S a S | \lambda$

Which statement is correct ?

• A. $G_{1}$ is unambiguous and $G_{2}$ is unambiguous.
• B. $G_{1}$ is unambiguous and $G_{2}$ is ambiguous. 
• C. $G_{1}$ is ambiguous and $G_{2}$ is unambiguous.
• D. $G_{1}$ is ambiguous and $G_{2}$ is ambiguous. 

Comments

https://gateoverflow.in/58010/ugcnet-june2013-ii-21

Answer 1

Both are ambiguous...

G1: S→AB|aaB

A→a|Aa

B→b

To generatte string "aab"

S->​AB ->AaB -> aaB -> aab  

S->aaB->aab

So ambiguous...

G2: S→aSbS|bSaS|λ​

Generate" abab "

S->aSbS -> abS->abaSbS -> abab 

S->aSbS->aSb->abSaSb ->abab

So ambiguous...