Peter Linz Edition 4 Exercise 4.3 Question 12 (Page No. 123)

Question

Apply the pumping lemma to show that $L=$ {$a^nb^kc^{n+k}:n\geq0,k\geq0$} is not regular.

Comments

String $aabbbccccc \in L$ .

According to pumping lemma for every $x \in L$ , the string can be divided into three parts $uvw$ .  Now if string $v$ is pumped any number of times , the pumped string should also belong to $L$.

Let $u='aa' \ v='bbb' \ w='ccccc'$.

If we pump v twice we get.

$aabbbbbbccccc$ , but this doesn't belong to $L$. Thus pumping lemma fails here , thus the language is not regular.

Answer 1

The given language is L= {abcc,aabccc,aabbcccc,.....}

the sum of number of a's and b's should be equal to number of c's.

let us consider s = abcc from the language L.

According to Pumping lemma, we divide string into 3 parts u,v,w . Let it be  u=a, v= b, w = cc.

Now ,Consider a string s' with v raised to any power > 1 , let power be 2: s'=abbcc. which doesn't belong to this language as the sum of number of a's and b's is not equal to number of c's.

So the given language is not a regular language.