Consider the context free grammar G S → SS + | SS*| b Consider the statements:…

Conclusion: Only S1 and S2 are true; S3 is false.

Leftmost derivation for the string bb+b*:

S => SS* => SS+ S* => bS + S* => bb + S* => bb + b*

So statement S1 is true.

Rightmost derivation for the string bb+b*:

S => SS* => Sb* => SS + b* => Sb + b* => bb + b*

So statement S2 is true.

Why the grammar is not ambiguous:

• Each derivation corresponds to a full binary tree where leaves are the terminal b and internal nodes are binary operators (+ or *).

• Postfix notation (the form produced by this grammar) encodes that binary tree uniquely, so a given postfix string determines a single parse tree.

• Therefore there is no string with two different parse trees; the grammar is unambiguous.

So statement S3 is false.

Also The statement S3 is FALSE because the grammar does not generate more than one parse tree for the same valid string.

For ambiguity, a grammar must allow:

• more than one leftmost derivation, or

• more than one rightmost derivation, or

• more than one parse tree

For the string bb+b*, only one valid grouping is possible:

(bb+)b∗

Since no alternative parse structure exists for the same string, the grammar is not ambiguous.