Assume
w = abababa.
The two derivation trees for w = abababa is shown below in Fig. (a) and (b).
Therefore, the grammar G is ambiguous.
Ì Exam ple 2.3.3: Show that the grammar G with production
S
a aAb abSb
A aAAb bS
→
→
|
|
|
is ambiguous.
Solu tion
S
abSb
S
abSb
abab
S
a
⇒
→
⇒
→
(
)
(
)
Q
Q
Similarly,
S
aAb
S
aAb
abSb
A bS
abab
⇒
→
⇒
→
⇒
(
)
(
)
Q
Q
Since ‘abab’ has two different derivations, the grammar G is ambiguous.
2.4 SIMPLIFICATION OF CFG
2.4.1 Sim pli fi ca tion of CFG-Intro duc tion
In a Context Free Grammar (CFG), it may not be necessary to use all the
symbols in V T
∪ , or all the production rules in P while deriving sentences.
Let us try to eliminate symbols and productions in G which are not useful
in deriving sentences.
Let G V T S P
= ( , , , ) be a context-free grammar. Suppose that P contains a
production of the form
A x B x
→ 1
2 .
Con text-free Grammars
131
S
S
S
S
S
b
b
S
S
S
S
S
b
a
S
S
b
a
a
a
S
S
b
a
a a
a
b
(a)
(b)