Mathematical Foundation of Computer Science

DHARM

286 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

S ⇒ a B ⇒ a b S ⇒ a b b A ⇒ a b b a S ⇒ a b b a a B

⇒ a b b a a b S ⇒ a b b a a b a B ⇒ a b b a a b a b

Assume the string ‘aabbabab’, and then following will be the derivation sequences.

l S ⇒ a B ⇒ a a B B ⇒ a a b b S ⇒ a a b b a B ⇒ a a b b a b S

⇒ a a b b a b a B ⇒ a a b b a b a b, (using lm derivatin sequence)

l S ⇒ a B ⇒ a a B B ⇒ a a b S B ⇒ a a b b A B ⇒ a a b b a B

⇒ a a b b a b S ⇒ a a b b a b a B ⇒ a a b b a b a b

(using lm derivation sequence)

Both derivation sequences are different and their derivation trees are shown in Fig. 11.9

S

a B

a B B

bba bab

S

a B

a B B

b babab

lm derivation sequence 1 lm derivation sequence 2

Fig. 11.9
Since the string has two derivation trees so grammar is ambiguous and the language it
generates is an ambiguous language.
Example 11.9. Construct the CFG for the language L = {ak bl ck/k ≥ 0, l ≥ 0}.
Sol. Since the language L = {∈, b, bb......, ac, aacc......, abc,......}, where,
l ε is in language and it derives from start symbol S hence ......
S → ∈ is a production
l strings ‘b, bb, bbb,......’ are derived from the productions
S → b or S → b S
l strings ‘ac, aacc, ......’ are derived from productions
S → a c or S → a S c
Remaining strings can be derived using above productions, i.e.,
For example,
S ⇒∈;S ⇒ b;S ⇒ b S ⇒ b b;S ⇒ b S ⇒ b b S ⇒ b b b and so on
S ⇒ a c;S ⇒ a S c ⇒ a a S c c ⇒ a a ε c c ⇒ a a c c; and so on.
S ⇒ a S c ⇒ a b c;S ⇒ a S c ⇒ a b S c ⇒ a b b c; and so on.
So, the responsible grammar for language L has the productions
S → ∈ | b | b S | a | a S c
Since, the productions fulfill the restrictions required for CFG, so the grammar is CFG.
Alternatively, if the language L = {ak bl ck/k ≥ 1, l ≥ 1} then the production
S → a S c