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

Derive string a-(a+a)/(a*a) using leftmost derivations and rightmost  derivations for  grammar S->S/S

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 :

LEFTMOST DERIVATION

S-> S/S

S -> S-S /S                              [ S->S-S ]

S-> a-S /S                               [S->a ]

S-> a- (S) /S                          [ S->(S)]

S-> a-(S+S) /S                      [ S->(S+S)]

S-> a-(a+S)/S                       [S->a ]

S-> a-(a+a)/S                       [S->a ]

S-> a-(a+a)/(S)                    [S->(S) ]

S-> a-(a+a)/(S*S)                [S->(S*S) ]

S-> a-(a+a)/(a*S)                [S->(a) ]

S-> a-(a+a)/(a*a)               [S->(a) ]

DERIVATION TREE

RIGHTMOST DERIVATION

S -> S-S 

S-> S-S/S                               [S-> S/S]

S-> S-S/(S)                            [S-> (S)]

S-> S-S/(S*S)                        [S-> S*S]

S-> S-S/(S*a)                           [ S->a ]

S-> S-S/(a*a)                              [ S->a ]

S-> S- (S)  / (a*a)                          [S-> (S)]

S-> S-(S+S) / (a*a)                       [S-> S+S]

S-> S-(S+a)/ (a*a)                          [ S->a ]

S-> S-(a+a)/ (a*a)                        [ S->a ]

S-> a-(a+a)/ (a*a)                        [ S->a ]

DERIVATION TREE

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

More Tutorials