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.