DHARM318 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCEASw
u yAS A y x x x wvvvu AA(d)(e)
Fig. 11.27 (Continued)
In the derivation trees we have seen that duplicates of A occur at the different node
points (not at the same node point) hence sub strings v and x together not be empty so,
| v. x | ≥ 1 proved cond. (i)
From the derivation tree it is also seen that non terminal A is chosen near or to the
bottom of the tree. So the largest path in the sub tree rooted at A is at most (k + 1). Hence, it
yields the string of length at most 2(k+1)–1. That is at most 2k or n.
Thus, | v. w. x | ≤ n proved cond. (ii)
Proved.
Now we solve some examples and see the application of pumping lemma to testify the
language whether it is a CFL or not CFL.
Example 11.31. A language L is defined over Σ = {a, b, c} s.t. L = {ai bi ci/i ≥ 1}. Prove that L is
not a CFL.
Sol. We suppose L is a CFL. Let’s take a constant n (for lemma) and assume a string Z ∈ L i.e.
| Z | ≥ n and Z = an bn cn, which can be break into sub strings u, v, w, x and y s.t.
Z = u. v. w. x. y
and satisfying the conditions (i), (ii) and (iii) of the pumping lemma.
Since | v. w. x | ≤ n , the string vwx can contain at most two distinct type of symbols viz.
(and since | v. x| ≥ 1, v and x together contain at least one)
l If stringv. w. x ∈ an then string u. w. y must have fewer than n a’s besides possible
n b’s and n c’s ⇒ string doesn’t contains equal numbers of all symbols.
l String v. w. x ∈ an bn; then vx consists of only a’s and b’s with at least one of the
symbols. So, uwy has n c’s but fewer than n a’s or fewer than n b’s or both ⇒ string
doesn’t contains equal numbers of all symbols.
l String v. w. x ∈ bn; so string ∉ L
l String v. w. x ∈ bn cn; ⇒ so string ∉ L
l String v. w. x ∈ cn; ⇒ so string ∉ L
Therefore, neither string is in the language L. Condition (ii) of lemma is violated, hence
L is not a CFL.