2.3.5 Ambig u ous Gram mars/Ambig u ous Lan guages
Since derivation trees, leftmost derivations, and rightmost derivations are
equivalent rotations, the following definitions are equivalent:
Definition: Let G
N T P S
= ( , , , ) be a CFG.
A string w L G
∈ ( ) is said to be “ambiguously derivable “if there are two or
more different derivation trees for that string in G.
Definition: A CFG given by G = (N, T, P, S) is said to be “ambiguous” if there
exists at least one string in L(G) which is ambiguously derivable. Otherwise it
is unambiguous.
Ambiguity is a property of a grammar, and it is usually, but not always
possible to find an equivalent unambiguous grammar.
An “inherantly ambiguous language” is a language for which no
unambiguous grammar exists.
Ì Exam ple 2.3.1: Prove that the grammar
S
aB ab
A aAB a
B
ABb b
→
→
→
| ,
| ,
|
is ambiguous.
Solu tion
It is easy to see that “ab” has two different derivations as shown below.
Given the grammar G with production
1
2
3
4
5
6
.
.
.
.
.
.
S
aB
S
ab
A aAB
A a
B
ABb
B
b
→
→
→
→
→
→
Using (2),
Using (1),
and then (6).
S
ab
S
aB
ab
⇒
⇒
⇒



 
Ì Exam ple 2.3.2: Show that the grammar S
S S S
a
→
→
| ,
is ambiguous.
Solu tion
In order to show that G is ambiguous, we need to find a w L G
∈ ( ), which is
ambiguous.
130
Theory of Automata, Formal Languages and Computation