Question

For a grammar G with the productions where G = ( {S, A, B}, {a, b}, S, P ) with productions

                                             S --> AB | bbbB,              A --> b | Ab,       B --> a..

1.Show that the grammar G is ambiguous.

2.Give language L that is generated by G, L = L(G), in a formal expression (including a regular expression).

3.Can you construct an unambiguous grammar that is equivalent to G? Otherwise, show that G is inherently ambiguous.

Answer 1

Ambiguity is verified by checking the leftmost derivation trees or parse trees , if for a string parse trees are more than one then it is ambiguous grammar.

So by substitution of A production into S...the ambiguity of string parse trees are removed.

Kindly comment for queries if any, upvote if you like it.

Thankyou.