# Ambiguity in Context Free Grammar - Automata

**Ambiguity in Context Free Grammar?**

**Context Free Grammar**

Context Free Grammar has one condition for production rules, which is, *on the left-hand side of each rule, there must be only single variable, and on the right-hand side there may be a combination of variables and terminals including **?.*

A Context Free Grammar G = (V, T, P, S) is said to be ambiguous, if there exists at least one string in L (G), which can be generated in different ways. **If the same string is generated by different ways, we can say that string is derived ambiguously**. This type of string will have different derivation tree or parse tree, and have several meanings.

**In other words**, “*a grammar G is ambiguous, if some string from grammar has more than one leftmost derivation and right most derivation tree.”*

These types of generated results are undesirable in any programming languages, because a given program should have a unique interpretation.

**Example 1:**

Consider the grammar G whose productions are:

S -> S1S

S -> 0

Prove that the above given grammar is ambiguous.

**Solution:**

To show that given grammar is ambiguous, we need to find a string w ? L (G).

Let w = 0101010.

1) Firstly, we check derivation of string using this

S => S 1 S

=> 0 1 S

=> 01S1S

=> 0101S

=> 0101S1S

=> 010101S

=> 0101010

The first derivation tree for string w = 0101010.

2) Now, we check derivation of string using this

S => S 1 S

=> S1S1 S

=> 01S1S

=> 0101S

=> 0101S1S

=> 010101S

=> 0101010

The second derivation tree for given string w = 0101010.

Both the derivation trees are different. Hence it is proved that given context free grammar G is **ambiguous.**

**Example 2:**

Consider the grammar G whose productions are:

S -> 1A0S

S -> 1A0S1S

A -> 1

S -> 0

Prove that the above given grammar is ambiguous.

**Solution:**

To show that given grammar is ambiguous, we need to find a string **w ****? L (G).**

Let w = 110110010.

1) Firstly, we check derivation of string using this, S => 1A0S

=> 110S

=> 1101A0S1S

=> 110110S1S

=> 11011001S

=> 110110010

The first derivation tree for string w = 110110010.

2) Now, we check derivation of string using this

S => 1A0S1S

=> 110S1S

=> 1101A0S1S

=> 110110S1S

=> 11011001S

=> 110110010

The second derivation tree for given string w = 110110010.

Both derivation trees are different, hence it is proved that given context free grammar G is **ambiguous.**

**Example 3:**

Consider the grammar G whose productions are:

S -> AA

A -> AAA

A -> 1A

A -> A1

A -> 0

Prove that the above given grammar is ambiguous or not for string 010.

**Solution:**

To show that given grammar is ambiguous we need a string w ? L (G).

Let w = 010.

1) Firstly we check derivation of string using this

S -> AA

=> 0A

=> 01A

=> 010

The first derivation tree for string w = 010.

2) Now, we check derivation of string using this

S -> AA

=> A1A

=> 01A

=> 010

The second derivation tree for given string w = 010.

Both derivation trees are different, hence it is proved that given context free grammar G is **ambiguous.**

**Example 4:**

Consider the grammar G whose productions are:

S -> AB

S -> 00B

A -> 0

A -> A0

B -> 1

Prove that the above given grammar is ambiguous or not.

**Solution:**

To show that given grammar is ambiguous we need to find a string w ? L (G).

Let w = 001.

For string w = 001, we can derive two different left most derivation tree from given grammar.

1) Firstly, we check left most derivation tree of string using this

S => 00B

=> 001

The first left most derivation tree for string w = 001.

2) Now, we check left most derivation tree of string using this

S -> AB

=> A0B

=> 00B

=> 001

The second leftmost derivation tree for given string w = 001.

Both derivation trees are different, hence it is proved that given context free grammar G is **ambiguous.**