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.