edited by
2,134 views
1 votes
1 votes

Which of the following grammars is(are) ambiguous?

  1. $s \rightarrow ss \mid asb \mid bsa \mid \lambda$
  2. $s \rightarrow asbs \mid bsas \mid \lambda$
  3. $s \rightarrow aAB \\ A \rightarrow bBb \\ B \rightarrow A \mid \lambda \text{ where } \lambda \text{ denotes empty string}$

Choose the correct answer from the options given below:

  1. $(i)$ and $(iii)$ only
  2. $(ii)$ only
  3. $(ii)$ and $(iii)$ only
  4. $(i)$ and $(ii)$ only
edited by

2 Answers

1 votes
1 votes

 

  1. s→ss∣asb∣bsa∣λ  ambiguous as  string λ can be obtained via 2  derivation tree
  2. s→asbs∣bsas∣λ   ambiguous as string  abab can be obtained via 2  derivation tree
  3. s→aAB,  A→bBb,  B→A∣λ   string abbbb can be derived via 2  derivation tree                                                   Hence all are ambiguous  no options correct
0 votes
0 votes
(C) is the language $ a b^{2n} $ where the $ b ^ {2n} $ can come from both $ A ~and ~ B ~ of ~ s → aAB $ Hence it is ambiguous.

(A) too has that same problem in that the string aabb can the derived from both the first or second s in $ S → SS $

(B) too is ambiguous from @SanjaySharma’s answer.

So all are ambiguous.
Answer:

Related questions