The Gateway to Computer Science Excellence
+3 votes
1.1k 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 Boss (30.1k points)
edited by | 1.1k 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 Boss (25.5k points)
selected by

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
50,648 questions
56,430 answers
195,211 comments
99,927 users