Pumping Lemma for Regular Languages

Pumping Lemma is applied to infinite languages to show that languages are not regular. It should never be used to prove that a language is regular. That’s why the pumping lemma is also called a negative test. A simple description of the pumping lemma is given in the following diagram.

Pumping Lemma Test (PLT) - For Regular Language

V. Important:

Point 01: Keep in mind that all finite languages are regular, and there is no need to check whether they are regular or not, but all infinite languages may or may not be Regular. For example, as a^n, b^n is an infinite language but not a Regular language. So, the Pumping Lemma Test is important to check whether infinite languages are regular or not.

 Main Methods to Determine if a Language is Regular

Although there are many methods to check whether the infinite languages are regular or not, the pumping Lemma is one of the most important.

Method Description
1. Pumping Lemma Used to prove a language is not regular by contradiction (using the “pumping property”).
2. Myhill–Nerode Theorem A powerful method that checks regularity based on the number of equivalence classes — finite ⇒ regular.
3. Finite Automaton Construction If you can build a DFA, NFA, or ε-NFA, then the language is regular.
4. Regular Expression Existence If a regular expression can be written for the language, it is regular.
5. Closure Properties Use known closure operations (union, concat, etc.) to build or break down a language into regular parts.
6. State Minimization (DFA) Helps in analyzing the DFA structure to determine regularity (used alongside Myhill–Nerode).

Pumping Lemma Conditions for Regular Languages

If L is a regular language, then there exists a constant p (called the pumping length) such that every string w in L with length at least p can be divided into three parts

w = xyz

Such that

  1. |y| ≥ 1
    (y is not empty — it contributes something to the string)

  2. |xy| ≤ p
    (The repetition part occurs within the first p characters)

  3. For all i ≥ 0, the string xyiz ∈ L
    (i.e., you can “pump” y — repeat it any number of times — and the string stays in the language)



Pumping Lemma Algorithm for Regular Language

Here is a descriptive diagram for the pumping lemma algorithm

Pumping Lemma Algorithm for Regular Languages

Tip: The pumping lemma gives the result of the failure of any condition. That’s why it is also called a negative test.

We can say,

  • If an infinite Language (L) does not satisfy all three conditions of the Pumping Lemma, then it is not a regular language.
  • If given an infinite Language that satisfies all three conditions of the Pumping Lemma, then it may or may not be a regular language.

Examples of Pumping Lemma For Regular Languages

Let’s explain some examples of the pumping Lemma for regular languages

Example 01: Using Pumping Lemma, prove that the language A = { yy | y ∈ {0,1}* } is not Regular

Below is a descriptive diagram that explains that why the language A = { yy | y ∈ {0,1}* } is not regular.

Example 01 - Pumping Lemma for Regular Languages

A straightforward, short description of the given example to prove that the language A = { yy | y ∈ {0,1}* } is not Regular is given below, by using different “p” and “i” values

  • We want to prove A = {yy | y ∈ {0,1}*} is not regular.
  • Assume it is regular and choose a string S = 0101 from A.
  • Let pumping length be p = 2, so |xy| ≤ 2 and |y| > 0.
  • Split: x = 0, y = 1, z = 01 → S = xyz = 0101.
  • Pump y: xy²z = 01101, which is not in the form yy.
  • So, pumping fails → A is not regular.



Example 02: Using Pumping Lemma prove that the language A = { anbn | n ≥ 0 } is not Regular

Below is a descriptive diagram that explains why the language A = { anbn | n ≥ 0 } is not regular.

Example 02 Pumping Lemma for Regular Languages

A straightforward, short description of the given example to prove that the language A = { anbn | n ≥ 0 } is not Regular is given below, by using different “p” and “i” values

  • We want to prove that A = { aⁿbⁿ | n ≥ 0 } is not regular.
  • Assume A is regular and let the pumping length be p = 3.
  • Choose a string S = aaabbb from A (n = 3).
  • Split S into x = aa, y = a, z = bbb, where |xy| ≤ p and |y| > 0.
  • Pump y: xy²z = aaaabbb, which has 4 a’s and 3 b’s → not in A.
  • So, the string after pumping is not in the language → A is not regular

Example 03: Using Pumping Lemma prove that the language A = { anb2n | n ≥ 0 } is not Regular

Below is a descriptive diagram that explains why the language A = { anb2n | n ≥ 0 } is not regular.

Example 03 Pumping Lemma for Regular Languages

A simple, short description of the given example to prove that the language A = { anb2n | n ≥ 0 } is not Regular is given below, by using different “p” and “i” values

  • We want to prove that A = { aⁿb²ⁿ | n ≥ 0 } is not regular.
  • Assume A is regular and let the pumping length be p = 3.
  • Choose a string S = aaabbbbbb from A (n = 3 → 3 a’s and 6 b’s).
  • Split S into x = aa, y = a, z = bbbbbb, where |xy| ≤ p and |y| > 0.
  • Pump y: xy²z = aaaabbbbbb, which has 4 a’s and 6 b’s → not in A (should be a⁴b⁸).
  • So, the string after pumping is not in the language → A is not regular

"Your Support, Our Priority"

"We Make It Easy"