Question

Consider a grammar: S --> | as SS SSb Sbs, Where T={a,b} V={S}. a. Show that the grammar is ambiguous. b. What is the language generated by this grammar?

Answer 1

Solution:

Given grammar:

S -> a | aS | bSS | SSb | SbS

(a)

Explanation:

Ambiguous grammar:

=>A grammar is called ambiguous if there exists more than one parse tree for a string.

let say strings at ab aa Rasse trees: s using postueting productims sbss sas sa a a a parse tree 2 S tring postetta s sbs s a s १ S spas a a a

=>For string abaa there exists two different parse tree hence we can say that the given grammar is ambigous.

(b)

Explanation:

=>Smallest string generated from the grammar = a using S -> a

=>String aa can be generated using S -> aS and S -> a

and so on.

=>Language of grammar(L(G)) = {a, aa, aaa, ..., baa, aab,...}

I have explained each and every part with the help of statements as well as image attached to it.