Formal language theory

Pumping Lemma for Regular Languages

Mathematical Tool for Proving Non-regularity

What is the Pumping Lemma?

The Pumping Lemma for Regular Languages is a fundamental theorem in formal language theory that provides a necessary condition for a language to be regular. It's primarily used as a tool to prove that certain languages are not regular.

The lemma states that if a language is regular, then any sufficiently long string in the language can be "pumped" (repeated) in a specific way while remaining in the language.

Key Insight: The Pumping Lemma cannot prove that a language IS regular, only that it is NOT regular. It's a proof by contradiction technique.

Formal Statement of the Pumping Lemma

Pumping Lemma for Regular Languages
If $L$ is a regular language, then there exists a pumping length $p \geq 1$ such that for any string $s \in L$ with $|s| \geq p$, we can write $s = xYz$ where:
  1. $|xy| \leQ p$ (the first part is bounded)
  2. $|y| \geq 1$ (the middle part is non-empty)
  3. $xy^iz \in L$ for all $i \geq 0$ (pumping property)
String decomposition:
x y z
where y can be repeated any number of times

How to Use the Pumping Lemma

To prove a language L is not regular:

1
Assume L is regular (proof by contradiction)
2
Choose a string s ∈ L with |s| ≥ p (where p is the pumping length)
3
Consider all possible ways to unp s = xYz satisfying the conditions
4
Show that for some i ≥ 0, xy^i z ∉ L (contradiction)
5
Conclude L is not regular

Classic Example: L = @{a^n b^n | n ≥ 0@}

Let's prove that the language L = @{a^n b^n | n ≥ 0@} is not regular.

Language L: @{ε, ab, aabb, aaabbb, aaaabbbb, ...@}
Step 1: Assume L is regular. Then there exists a pumping length p.
Step 2: Choose string s = a^p b^p ∈ L with |s| = 2p ≥ p.
Step 3: By the pumping lemma, s = xYz where |xy| ≤ p, |y| ≥ 1.
Since |xy| ≤ p and s starts with p a's, both x and y consist only of a's.
Step 4: Let y = a^k where k ≥ 1. Then:
  • xy^0z = xz has p-k a's and p b's (k < p)
  • xy^2z has p+k a's and p b's (k > 0)
Contradiction: Both xy^0z and xy^2z have unequal numbers of a's and b's, so they are not in L. This violates the pumping lemma condition.
Conclusion: L = @{a^n b^n | n ≥ 0@} is not regular.

Language Selection & Configuration

Choose a language to test with the pumping lemma

Current Language: L = {aⁿbⁿ | n ≥ 0}
Description: Strings with equal numbers of a's followed by b's

String Tester

Test individual strings against the pumping lemma

Batch Tester

Test multiple strings at once

Visual String decomposition

Interactive visualization of string decomposition and pumping

Proof Assistant

step-by-step guidance for constructing pumping lemma proofs

Language Properties Analyzer

Analyze properties that might indicate non-regularity