Interesting Problem 2 : Pumping Lemma

1. Show that the language {an bcba2n : n ≥ 0} is not regular using the pumping lemma.

Ans. If the Language L = an bcba2n is regular than it can be converted into string w where w = xyz . so we have that xyz = an bcba2n . Now since y ≠ € , there can be three cases .

Case 1 : Now assume y is having an instance of a and z will have the rest of bcba2n . Now according to pumping lemma we will have xyⁱz where i ≥ 0 , will also lies in L but if i = k , then we can increase the instances of a without increasing the instance of a present in substring z . So it can’t be a regular language .

Case 2: Now assume that y = bcb , in that case . xyⁱz when i = 0 will not have any instance of bcb . so the resulting language would be falling in L . Hence L can’t be a regular language.

Case 3: Now assume that y is having an instance of a present after bcb . in that case x = aⁿbcb , y = a^k , z = a^2n-k . Now according to pumping lemma xyⁱz where i≥0 , should lie in L . Now if we increase the value of i , we can have more instances of a in the later part which violates the property of L having exactly double number of instances of a present in the substring x . Hence L can’t be a regular language.

As none of the case is able to provide valid proof of pumping lemma L can’t be a regular language.