The Gateway to Computer Science Excellence
+3 votes
1.4k views

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 ?

  1. $G_{1}$ is unambiguous and $G_{2}$ is unambiguous.
  2. $G_{1}$ is unambiguous and $G_{2}$ is ambiguous. 
  3. $G_{1}$ is ambiguous and $G_{2}$ is unambiguous.
  4. $G_{1}$ is ambiguous and $G_{2}$ is ambiguous. 
in Theory of Computation by
edited by | 1.4k views

1 Answer

+3 votes
Best answer

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...

by
selected by
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,517 answers
201,939 comments
95,368 users