Question

Show the following Grammar is Ambiguios :

S -> TU | SbS | SS

T -> Tb | aT | ^

U -> aU | ^

Answer 1

S -> TU | SbS | SS

T -> Tb | aT | ^

U -> aU | ^

Given grammar is CFG. For CFG, ambiguity is undecidable problem.

So need to take various input strings and test.

Let’s go here

String: a^b^

Derivation:

S->TU

->TbU

->aTbU

->a^bU

->a^b^

S->TU

->aTU

->aTbU

->a^bU

->a^b^

Two different parse trees are generated for the one string. So given grammar is Ambiguous grammar.

comment below if you have any doubt