The Gateway to Computer Science Excellence
+1 vote
1.1k views

Given the production rules of a grammar G1 as

$S_1 \rightarrow AB \mid aaB$

$A \rightarrow a \mid Aa$

$B \rightarrow b$

and the production rules of a grammar G2 as

$S_2 \rightarrow aS_2bS_2  \mid bS_2 aS_2 \mid \lambda$

Which of the following is correct statement?

  1. G1 is ambiguous and G2 is not ambiguous
  2. G1 is ambiguous and G2 is ambiguous
  3. G1 is not ambiguous and G2 is ambiguous
  4. G1 is not ambiguous and G2 is not ambiguous
in Compiler Design by Veteran (105k points)
recategorized by | 1.1k views

1 Answer

+2 votes
Best answer

Here both G1 and G2 are ambiguous 

G1 : We can generate 2 parse tree for string aab

 

                S1                                                               S1

             /    \                                                             /  |  \

          A       B                                                          a   a    B

        /    \         \                                                                   \

     A        a          b                                                                  b

  /

a

G2: We can generate more than one parse tree for abab , baba etc.

        

Hence,Option(B)G1 is ambiguous and G2 is ambiguous .

by Boss (41.2k points)
selected by
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,737 questions
57,321 answers
198,400 comments
105,155 users