Question

E={a,b,c,d}, L = {anbmchdm : n, m 2 0}. For example, s = aabccd e L because the symbols are in Unicode order, and #a(s) = #c(s), #(s) #c(s), #b(s) = #a(s); ac e L for the same reason; s = abcdd & L because #b(s) #a(s); and acbd & L beause the symbols are not in Unicode order. Prove that L & CFLs using the CF pumping theorem, starting by defining w such we Land |w| 2 k. Remember that you cannot chose a literal value for w, and that the only property you can assume for k is that k 1. For each possibility for v & y consistent with the two CF pumping theorem guarantees, show that w can be pumped to generate w'& L. End your proof with a conclusion stating why L & CFLs. The same conclusion would be valid for all CF pumping theorem proofs, except possibly for the symbol representing the language.

Answer 1

The pumping lemma of a context free language is defined as :

If L is a context free language then L has a pumping length k such that any string w where |w| >= k can be divided into 5 parts as L = uvxyz and the following 3 conditions hold true :

• u v^i x y^i z is in L for every i >= 0.
• |vy| > 0
• |vxy| <= k

The given language L is :

L = { a^n b^m c^n d^m : n, m >= 0 }

Let the pumping length be k and the string used be w = a^p b^2p c^n d^2p.

Let the value of k be 4.

Then,

w = a^4 b^8 c^4 d^8

According to pumping lemma, the string w is divided as :

w = u v x y z

Assume that the given langauge is context free.

The following cases are evaluated in order to implement the pumping lemma :

Case 1 :

v contains only one kind of symbol and y also contains only one type of symbol.

w = a^4 b^8 c^4 d^8 = u v x y z

a aa a bbbbbbbbccccd d d d d d d d JUUL u V X y Z

u = aaa

v = a

x = bb

y = b

z = bbbbbccccdddddddd

According to the first condition of pumping lemma, u v^i x y^i z is in L for every i >= 0.

Let i = 2,

then, w = u v^i x y^i z =  u v^2 x y^2 z = aaaaabbbbbbbbbccccdddddddd = a^5 b^b^9 c^4 d^8. Here,the powers of a and c don't match and also the powers of b and d don't match. So, this is not in L.

Case 2 :

v consists of more than one kind of symbol or y consists of more than one kind of symbol.

w = a^4 b^8 c^4 d^8 = u v x y z

a aa a bbbbbbbbccccd d d d d d d d и уху Z

u = aaa

v = ab

x = b

y = b

z = bbbbbccccdddddddd

According to the first condition of pumping lemma, u v^i x y^i z is in L for every i >= 0.

Let i = 2,

then, w = u v^i x y^i z =  u v^2 x y^2 z = aaaababbbbbbbbbccccdddddddd but this is not in L.

Both the cases contradict the assumption that the language L is context free.

Hence, it is proved that the given language L is not a context free language.