Explain ambiguous and unambiguous context free grammar with example.

Sure, let's start with the definitions:

1. Ambiguous Context Free Grammar: A context free grammar is said to be ambiguous if there exists a string that can be derived in more than one way i.e., the string has more than one parse tree or leftmost derivation.

Example: Consider the grammar G = ({S}, {a, b}, P, S) where P is the set of productions given by:

S -> SS | aSb | ε

The string "aabb" can be derived in two different ways:

• S -> SS -> aSbS -> aSb -> aaSbb -> aabb
• S -> SS -> SaSb -> aaSbb -> aabb

So, this grammar is ambiguous.

2. Unambiguous Context Free Grammar: A context free grammar is said to be unambiguous if there exists only one parse tree or leftmost derivation for any string derived from the grammar.

Example: Consider the grammar G = ({S}, {a, b}, P, S) where P is the set of productions given by:

S -> aSb | ε

The string "aabb" can be derived in only one way:

• S -> aSb -> aaSbb -> aabb

So, this grammar is unambiguous.

In summary, the difference between ambiguous and unambiguous context free grammar lies in the number of parse trees or leftmost derivations a string can have. If a string derived from the grammar can have more than one parse tree or leftmost derivation, the grammar is ambiguous. If a string can have only one parse tree or leftmost derivation, the grammar is unambiguous.