recategorized by
3,594 views
3 votes
3 votes

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
recategorized by

1 Answer

Best answer
4 votes
4 votes

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 .

selected by
Answer:

Related questions

1 votes
1 votes
1 answer
1
go_editor asked Jul 14, 2016
3,809 views
The equivalent production rules corresponding to the production rules $S \rightarrow S \alpha_1 \mid S \alpha_2 \mid \beta_1 \mid \beta_2$ is$S \rightarrow \beta_1 \mid \...
1 votes
1 votes
1 answer
2
go_editor asked Jul 14, 2016
2,179 views
The $mv$ command changesthe inodethe inode-numberthe directory entryboth the directory entry and the inode
3 votes
3 votes
1 answer
4
go_editor asked Jul 14, 2016
4,037 views
A virtual memory based memory management algorithm partially swaps out a process. This is an example ofshort term schedulinglong term schedulingmedium term schedulingmutu...