Pumping Lemma Proof Examples

Prove the following languages are not regular

a) L = a^R b^R

Detailed Mathematical Proof (You don’t have to do this in the exam, just read it to understand the concept. Then read the shorter proof after this, that’s what you should do)

First step: pick a w from L in terms of N.

w = xyz = a^N/2 b^N/2

This w is in L because it’s a number of a’s followed by an equal number of b’s. This w is ok, it’s going to work but an easier choice would be w = a^Nb^N then there would be only one case for y and the proof would be the same as for the next language when w = a^Nb^N .

Second step: define the possible cases for y.

All the a’s in w form region 1. All the b’s in w form region 2.

There are three possible cases.

Case 1: y is in region 1

Case 2: y is across region 1 and region 2

Case 3: y is in region 2

Third step: prove that for all cases, there’s a contradiction to the pumping lemma theorem i.e. there exists a q such that xy^qz is not in L.

Case 1: y is in region 1.

x is before y and therefore must also be in region 1.

x = a^p ( x is an unknown number of a’s)

y = a^s (y is an unknown number of a’s)

z = a^N/2-(p+s) b^N/2 (z is everything in w after x and y)

w = xyz = a^N/2b^N/2

Pump up or down, in this case it doesn’t matter. Choosing to pump up, q has to be greater than 1.

Pump up, q = 2.

xy²z = a^p (a^s)² a^{N/2 - (p+s)} b^N/2

= a^p a^s a^s a^{N/2 - (p+s)} b^N/2

= a^{p+s+s+ N/2 - p-s} b^N/2

= a^{N/2 +s} b^N/2

According to the conditions of the theorem y can not be equal to epsilon.

So |y| > 0 => s >0 => N/2 + s > N/2 => More a’s than b’s => xy²z is not in L.

Case 2: y is across regions 1 and 2

x is before y therefore must be in region 1.

x = a^{N/2 – s} ( choose y first, x is all the a’s in w before y)

y = a^sb^p (y is an unknown number of a’s and b’s)

z = b^{N/2 - p} (z is everything in w after x and y)

w = xyz = a^N/2b^N/2

In this case must pump up. If pump down, may remove an equal number of a’s and b’s and the string will still be in the language.

Pump up, q = 2

xy²z = a^{N/2 – s} (a^s b^p)² b^{N/2 – p}

= a^{N/2 – s} a^s b^p a^s b^p b^{N/2 – p}

= a^{N/2 – s + s} b^p a^s b^{p + N/2 –p}

= a^N/2 b^p a^s b ^N/2

According to the conditions of the theorem y can not be equal to epsilon.

So |y| > 0 => s+p >0 => either (p > 0 and s = 0) (same as case 3) or

(s > 0 and p = 0) (same as case 1) or

(p > 0 and s > 0)

if (p>0 and s=0) => more b’s than a’s => not in L

if (s>0 and p=0) => more a’s than b’s => not in L

if (p>0 and s>0) => wrong order, all a’s should be before all b’s=>not in L

xy²z is not in L.

Case 3: y in region 2

x is before y.

x = a^N/2 b^p (choose y first, x is everything in w before y)

y = b^s ( y is an unknown number of b’s)

z = b^{N/2 – (p+s)} (z is everything in w after xy)

w = xyz = a^N/2b^N/2

Pump up or down, in this case it doesn’t matter. Choosing to pump down, q has to be equal to 0.

Pump down, q = 0.

xy⁰z = a^N/2 b^p (b^s)⁰ b^{N/2 – (p+s)}

= a^N/2 b^p b^{N/2 – (p+s)}

= a^N/2 b^{p + N/2 – p – s}

= a^N/2 b^{N/2 - s}

According to the conditions of the theorem y can not be equal to epsilon.

So |y| > 0 => s >0 => N/2 > N/2 - s => More a’s than b’s => xy⁰z is not in L.

Since for all cases, there is at least one q for which xy^qz is not in L, L is not a regular language.

Shorter proof:

w = a^N/2 b^N/2

This w works but the proof would be easier if w = a^Nb^N. The proof would be the same as the next example when w = a^Nb^N.

All the a’s in w form region 1 and all the b’s form region 2.

There are three cases for y.

Case 1: y is in region 1. Pumping up, q=2 => more a’s than b’s => xy²z not in L

Case 2: y in region 1 and region 2. Pumping up, q=2 => in wrong order => xy²z not in L

Case 3: y in region 2: Pumping down, q = 0 => Fewer b’s than a’s => xy⁰z not in L.

Since for all cases, there exists a q such that xy^qz is not in L, L is not regular

b) L = { g | #_a(g) = #_b(g)}

Note: the number of a’s and b’s have to be equal but order doesn’t matter.

Example of a bad choice for w:

w = a^N/2 b^N/2

All the a’s in w form region 1, all the b’s in w form region 2.

There are three cases for y.

Case 1: y is in region 1. Pump down, q = 0. Fewer a’s than b’s. xy⁰z is not in L

Case 2: y is in region 1 and region 2.

Pumping down doesn’t work because may remove equal number of a’s and b’s. Pumping up doesn’t work because may add equal number of a’s and b’s, will be adding b’s followed by a’s in the middle of the string but for this language order doesn’t matter, so it will still be in the language.. try something else.

A good choice for w:

w = a^N b^N

All the a’s in w form region 1, all the b’s in w form region 2.

There is only one case for y, since |xy| ≤ N, y must be in region 1.

case 1: y in region 1. Pump up, q = 2. More a’s than b’s. xy²z is not in L.

Since there exists a q such that xy^qz is not in L, L is not regular.