Ambiguous Grammar | leftmost and rightmost derivations | theoretical computer science | Example 2

Derive string a+a*a using leftmost derivations and rightmost derivations for grammar. 

Ambiguous Grammar:

A context free grammar (CFG) is called as ambiguous if there is at least 1 string in L(G) having 2 or more distinct derivations .

Production rules:

S-> S+S | S-S |S*S | S/S |(S) | a

Solution :

RIGHTMOST DERIVATION 1

S-> S+S           [ S->S+S]

S->S+S*S        [ S->S*S]

S->S+S*a        [S->a]

S->S+a*a        [S->a]

S-> a+a*a       [S->a]

DERIVATION TREE

RIGHTMOST DERIVATION 2

S-> S*S

S-> S*a                   [S->a]

S-> S+S*a               [ S->S+S]

S->S+a*a                [S->a]

S->a+a*a                [S->a]

DERIVATION TREE

As there are 2 different  derivation and derivation trees, the grammar is ambiguous .

More Tutorials