Prove that the following grammar G is ambiguous S aSb bSa

Prove that the following grammar G is ambiguous.

   S --> aSb | bSa | SS | 1

   Describe L( G).

Solution

S --> aSb | bSa | SS | 1

a string w, let’s denote with w ^R the reverse of w ,if w = bba then w ^R = abb .Therefore, given a string w, let’s denote with ¯w or w\' the “complement” of w obtained from w by swapping a’s with b’s , . if w = bba then w\' = aab .we can define our language over the alphabet = {a, b} .

  L = {z | w : z = ww\'^R}

A grammar G = (V, , R, S) where all the productions in R is called left grammar form in e form in A aB and A c

A grammar G = (V, , R, S) where all the productions in R is called right grammar in form of e form A Ba and A c

that a left grammar define a regular language. We want to show that a right grammar define a regular language Let G = (V, , R, S) be a left grammar. Consider the grammar G = (V, , R , S), where R is obtained reverting all the productions.

G is a right grammar, since it was obtained reverting all the productions of the left grammar G. Moreover, it holds that L(G) = L(G ) r