Pumping Lemma

The Pumping Lemma for regular languages is a tool used to prove that a language is not regular. 

• It says: if $L$ is regular, there is a constant $p$ (pumping length) such that any string $s$ in $L$ with $|s| \ge p$ can be split into three parts $s = xyz$ where:

  1. $y \ne \epsilon$(middle part is non-empty)

  2. $|xy| \le p$ (loop happens early)

  3. $xy^i z \in L$ for all $i\ge \mathrm{0\; (loop\; can\; be\; pumped\; any\; number\; of\; times)}$

This property comes directly from the pigeonhole principle applied to the finite states of a DFA.

Note: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.

Formal Statement

If $L$ is a regular language, then there exists an integer $p$ (called the pumping length) such that any string $s$ in $L$ with $\mathrm{\mid }s\mathrm{\mid }\ge p$ can be written as:

$$s = xyz$$

where:

1. $\mathrm{\mid }y\mathrm{\mid }\ge \mathrm{1\; (i.e., }$$y$ is not empty),

2. $|xy| \le p$(i.e., the “loop”—$y$—occurs within the first $p$ characters),

3. For all $i \ge 0$, $xy^i z \in L$ (i.e., you can pump $y$ any number of times, and the resulting string stays in $L$)

A property that every regular language must satisfy, based on the fact that a DFA has only a finite number of states, so sufficiently long strings must repeat states and form loops

Explanation ( unformal proof)

1. If A is a regular language, then some DFA M decides the language.
2. Let p be the number of states in M.
3. Consider any string s∈ A with length greater than or equal to p. The characters in s will cause the machine to transition through a number of states, eventually reaching an accepting state after the last character in s.
4. Because the number of characters in s equals or exceeds the number of states in M, the machine will pass through at least one state more than once as M reads s. That is, the path that s traces through the machine has at least one loop in it.
5. For this argument we will use the first repeated state along the path: we will circle back around to that state for the first time before we have processed p characters.
6. We divide our path into three parts: x is the portion of s that leads from the start state to the first occurance of the repeated state. y is the part of s that traces the loop back around to the repeated state. z is the final part of s that takes us eventually to the accepting state.
7. M will now accept any string of the form xy^iz for i ≥ 0, because such a string takes M from start to the repeated state, goes i times around the loop back to the repeated state, and then runs from the repeated state on to the accepting state.

Proof  (via DFA and Pigeonhole Principle)

Follows the classic DFA-based argument:

• Let $M=(Q,\mathrm{\Sigma },\delta ,q_0,F)\; be\; a\; DFA\; recognizing$$L$.

• Set $p = |Q|$, the number of states in $M$.

• Consider any string $s \in L$ with $|s| \ge p$.

• As $M$ processes $s$, it transitions through $|s| + 1$ states. By the pigeonhole principle, since there are only $p$ distinct states, some state must repeat within the first $p+\mathrm{1\; visited\; states.}$

• Decompose $s$ as:

  • $x$: the prefix leading up to the first occurrence of that repeated state,

  • $y$: the substring that loops from the first to the second occurrence of that same state,

  • $z$: the remaining suffix.

• This guarantees:

  1. $y$ is non-empty (it represents at least one transition),

  2. $|xy| \le p$,

  3. Pumping $y$—i.e., repeating it—keeps the machine in the same looped state and thus $xy^i z \in L$ for all $i$
     

Use of the Pumping Lemma

• Main purpose: To prove a language is not regular.

• How:

1. Assume $L$ is regular.

2. Apply the lemma to a carefully chosen string $s$ in $L$.

3. Show that pumping $y$ breaks the property of the language.

4. Conclude $L$ is not regular (proof by contradiction).

NOTE: 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.

Detailed Examples

Language: $L=\{a^n{b}^n\mid n\ge 0\}<br>$

Goal: Show L is not regular.

1. Assume $L$ is regular.

2. Let $p$ be the pumping length given by the lemma.

3. Choose the specific string $s = a^p b^p$, which is in $L$ and satisfies $|s| \ge p$.

4. According to the lemma, $s = xyz$ with:

   • $|xy| \le p$ — so $x$ and $y$ consist only of $a$s,

   • $|y| \ge 1$ — $y = a^k$ for some $k \ge 1$.

5. Pump with $i = 0$:
   $xy^0 z = xz = a^{p-k} b^p$.
   Now the number of $a$s (which is $p \!-\! k$) is not equal to the number of $b$s ($p$), so $xz \notin L$.

6. This contradicts the pumping lemma’s requirement that $xy^i z \in L$ for all $i$.
   Thus, $L$ cannot be regular—proof by contradiction is complete.

• 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

A simple, short description of the given example to prove that the language A = { anb2n | n ≥ 0 } is not Regular is given below

• 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

A straightforward, short description of the given example to prove that the language A = { yy | y ∈ {0,1}* } is not Regular is given below

• 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.