Thursday, March 08, 2012

Pumping Lemma For Regular languages

For any infinite regular language, there exists some positive integer m such that for any w belongs to L with w >=m, it can be decomposed as :

For, W = XYZ
with |XY| <=m and |Y|>=1

such that W = [XY^iZ] , i=0,1,2,3, also in L

One of the applications of pumping lemma is that we can use it to prove whether the language is regular or not.

L = {a^nb^n | n>=0} is not regular

Proof :-

Assume L is regular
Lets assume a pumping length be m
Considering a word W in L = a^mb^m According to Pumping lemma W can be partitioned into three parts XYZ such that |XY|<=m and |y|>=1

Since we know that |XY|<=m and |y|>=1 there should be at least one a in Y. For any number m, Y would be a^m

if Y = a^m this implies that X = a^n-m

Testing for range of values of power of i

if i =1 we have W = [ a^n-m a^1m b^n ] belongs to language.

similarly, for i=2

We have W as a^n-m a^2m b^n = a^n+m b^n where number of a's are greater than b, hence does not belongs to the language.