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.

Ambiguity in Context Free Grammar

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.

Ambiguity in Context Free Grammar

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.

Ambiguity in Context Free Grammar

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.

Ambiguity in Context Free Grammar

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.

Ambiguity in Context Free Grammar

2) Now, we check derivation of string using this

 S -> AA

   => A1A

   => 01A

   => 010

The second derivation tree for given string w = 010.

Ambiguity in Context Free Grammar

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.

Ambiguity in Context Free Grammar

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.

Ambiguity in Context Free Grammar

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

Pin It on Pinterest

Share This