Grammar is ambiguous. S → aSbS|bSaS|∈

RGPV 2020
Show that the following grammar is ambiguous. 
S → aSbS|bSaS|∈

Ans. For grammar to be ambiguous, there should be more than one parse tree for same string.

Above grammar can be written as

S → aSbS

S → bSaS

S → ∈

Lets generate a string 'abab'.

So, now parse tree for 'abab'.

Left most derivative parse tree 01

S → aSbS

S → a∈bS

S → a∈baSbS

S → a∈ba∈b∈

S → abab

Parse Tree 01

Left most derivative parse tree 02

S → aSbS

S → abSaSbS

S → ab∈aSbS

S → ab∈a∈bS

S → ab∈a∈b∈

S → abab

Parse tree 02

So there are more than 1 parse tree for same string, that means grammar is ambiguous.