Q53: Inherently ambiguous language

Question #53: Consider the following language:

Is it possible to write unambiguous CFG for the above language?

 

Options:

1. Yes, the following language is unambiguous for L.

 

2. No, we can write the CFG but it is ambiguous. For instance,

 

3. We can’t have a CFG for this language.

4. None of the above.

 

Solution:

There is no possible unambiguous grammar for this language. In other words, this language is inherently ambiguous. The correct answer is option 2.