Skip to content
Home » Pumping Lemma

Pumping Lemma

The Pumping Lemma is an important concept in Theory of Computation used mainly to prove that a language is not regular.

1. Simple Definition

The Pumping Lemma says:

If a language is regular, then every sufficiently long string in that language can be divided into parts so that one part can be repeated (pumped) any number of times and the resulting string still belongs to the language.

In simple words:

A regular language has a repetitive part.


2. Pumping Lemma Statement

If L is a regular language, then there exists a positive integer p called the pumping length, such that every string w ∈ L with:\[ |w| \geq p \]

can be divided as:\[ w = xyz \]

such that:

Condition 1:

\[ |xy| \leq p \]

Condition 2:

\[ |y| > 0 \]

Condition 3:

\[ xy^iz \in L \]

for all:\[ i \geq 0 \]


3. Meaning of x, y, z

Suppose:\[ w=xyz \]

Then:

  • x = first part
  • y = middle part that can be repeated
  • z = remaining part
  • y must not be empty.
  • We can repeat y 0, 1, 2, 3… times.

For example:\[ xyz \]

If \(y\) is pumped:

iResult
0xz
1xyz
2xyyz
3xyyyz

If the language is regular, all these strings must remain in the language.


4. Why Do We Use Pumping Lemma?

The main use is:

To prove that a language is NOT regular.

The basic idea is:

  1. Assume the language is regular.
  2. Apply Pumping Lemma.
  3. Choose a suitable long string.
  4. Divide it into \(xyz\).
  5. Pump \(y\).
  6. Show that the resulting string is not in the language.
  7. Therefore, our assumption was wrong.
  8. Hence, the language is not regular.

Memory Trick:

Assume Regular → Pump → Break → Not Regular


5. Simple Example

Consider:\[ L=\{0^n1^n \mid n\geq0\} \]

This language contains:\[ \epsilon,\ 01,\ 0011,\ 000111,\ 00001111,\ldots \]

It means:

Number of 0s must be equal to number of 1s.

We want to prove that this language is not regular.

Step 1: Assume L is regular

Suppose L is regular.

Let pumping length be p.

Choose:\[ w=0^p1^p \]

This string belongs to L.


Step 2: Divide w into xyz

According to Pumping Lemma:\[ w=xyz \]

and:\[ |xy|\leq p \]

Since the first p symbols are all 0s, both x and y are within the 0s.

Therefore:\[ y=0^k \]

where \(k>0\).


Step 3: Pump y

Take:\[ i=0 \]

This removes y.

So we get:\[ xz=0^{p-k}1^p \]

Now:\[ \text{Number of 0s} \neq \text{Number of 1s} \]

Therefore:\[ xz\notin L \]


Step 4: Conclusion

This contradicts the Pumping Lemma.

Therefore:\[ \boxed{L=\{0^n1^n\mid n\geq0\}\text{ is not regular}} \]


6. Important Conditions to Remember

For:\[ w=xyz \]

remember these 3 conditions:

ConditionMeaning
(xy
(y
\(xy^iz\in L\)Pumping y should keep string in L

Fast Memory:

XY ≤ P, Y ≠ ε, Pump stays in L


7. Important Point for Exams

The Pumping Lemma is generally used to show:\[ \boxed{\text{Language is NOT Regular}} \]

It is not normally used to prove that a language is regular.

Also remember:

If a language is regular, it must satisfy the Pumping Lemma.

But simply finding one decomposition that works does not prove regularity; for a non-regularity proof, you must show that every valid decomposition can be made to fail by a suitable pumping choice.


Exam Answer — 5–10 Marks

Pumping Lemma is a theorem used in Theory of Computation to prove that certain languages are not regular.

It states that if \(L\) is a regular language, then there exists a positive integer \(p\), called the pumping length, such that every string \(w\in L\), where \(|w|\geq p\), can be divided into three parts:\[ w=xyz \]

such that:

  1. \(|xy|\leq p\)
  2. \(|y|>0\)
  3. \(xy^iz\in L\), for every \(i\geq0\)

The part \(y\) is called the pumping part because it can be repeated any number of times.

The Pumping Lemma is mainly used to prove that a language is not regular.

For example:\[ L=\{0^n1^n\mid n\geq0\} \]

is not regular because pumping the 0s changes the number of 0s without changing the number of 1s, violating the condition that both numbers must be equal.

One-line memory trick:

“Take a long string → divide XYZ → pump Y → if language breaks, it is NOT regular.”