Mathematical Foundation of Computer Science

DHARM

290 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

There exists another right most derivation sequence for the string ‘a + a H a’, i.e.,

S ⇒ S + S ⇒ S + S H S ⇒ S + S H a ⇒ S + a H a ⇒ a + a H a.

For above rm derivation sequence the rm derivation tree is shown in Fig. 11.15.

S

SS+

a SSH

aa

Fig. 11.15

Hence, the string ‘a + a * a’ has two lm & two rm derivation trees.

11.7 Ambiguous Grammar......................................................................................................

As we have seen that the derivation tree provides the structure of construction for the strings

in its language. This structure is unique for each string that is in the language. Although, few

grammars fails to provide a unique structures for all the strings that are in its language. We

mean to say that, such grammar’s language contains at least one string that has two or more

essentially different derivations. Those grammars are known as ‘ambiguous grammars’.

11.7.1 Definition

A grammar is said to be ambiguous if, for its any one string, produce at least two distinct
derivation tree either two distinct rm derivation tree or two distinct lm derivation tree.
So, a context free grammar G is said to be ambiguous if we can find two or more different
parse tree for at least a string ∈ L (G).
If each string has one and only one derivation tree (derived either by lm derivation
sequences or rm derivation sequences) then the grammar is an unambiguous grammar.

11.7.2 Ambiguous Context Free Language..................................................................

A context free language L is said to be ambiguous if and only if, every CFG generating L is
ambiguous.
Above definition says that the CFG grammars that are responsible for generating the
language L must be all ambiguous CFGs.
That is, if context free language L can be generated from CFG G 1 , G 2 , G 3 ... GK then L is
ambiguous context free language (CFL) iff ∀Gi(i = 1 to k) are ambiguous CFGs.
Example 11.12. Let G be the CFG with the productions
S → T + S/T
T → F H T/F
F → a/(S)
Test the ambiguity of G.
Sol. We take the string ‘a + a H a’ that is in L(G) and construct its most possible
derivation sequences, i.e.,