AMBIGUOUS AND UNAMBIGUOUS GRAMMARS || Context Free Grammar- Formal Languages Automata Theory

·         A CFG is ambiguous, if for at least one word in its CFL, there are two possible derivations of the word that correspond to two different syntax or parse trees.

·          A grammar is said to be ambiguous, if its language contains some string that has two different parse trees.

·         A grammar is said to be unambiguous, if its language has exactly one parse tree.

·         If grammar G is ambiguous, then for some w in L(G),there exists more than one parse tree. Hence, there is more than left most order of derivation and equivalently, there is more than one right most order of derivation.

·         If grammar G is ambiguous, then for some w in L(G),there exists more than one parse tree. Hence, there is more than left most order of derivation and equivalently one right most order of derivation.

Note : A grammar is ambiguous if there are more than one left most (or right most) derivation for given w.

Example:

a.   Consider a grammar for arithmetic expressions:

          E->a\b

          E->E-E

This grammar is ambiguous, because, to derive the string w=a-b-a, there exist two distinct parse trees, as shown in figure:

Fig:  Two distinct parse trees for the derivations of string w=a-b-a.

There are two distinct parse trees, which means that there are two distinct left or right most derivations.

Left most derivations:

(i)          E E-E a-E-E a-b-E a-b-a.

(ii)         E E-E E-E-E a-E-E a-b-E a-b-a

The same is the case with right most derivation.

a.   Consider the grammar

            S->aS/a where   V={S} and T= {a}.

This grammar is unambiguous because to derive the string w=aa, there exists exactly one parse tree, as shown in figure :

There is exactly one parse tree and hence, exactly one left most or right most derivation.

    Left most derivation: S a S aa.

    Right most derivation: S a S aa.