Statement of the Pumping Lemma

Theorem: If $L$ is a regular language, then there exists a constant $p \geq 1$ (the pumping length) such that any string $s \in L$ with $|s| \geq p$ can be divided into three parts $s = xyz$ satisfying:

1. Length constraint: $|xy| \leq p$
2. Non-empty pump: $|y| > 0$ (i.e., $y \neq \epsilon$)
3. Pumping condition: For all $i \geq 0$, $xy^iz \in L$

Important

The Pumping Lemma provides a necessary but not sufficient condition for regularity.

Understanding the Components

String Decomposition

For any sufficiently long string $s \in L$:

• $x$: Prefix (possibly empty)
• $y$: Pumpable substring (must be non-empty)
• $z$: Suffix (possibly empty)

Pumping Operation

The lemma guarantees that we can "pump" the $y$ part:

• $i = 0$: Remove $y$ (string becomes $xz$)
• $i = 1$: Original string (string becomes $xyz$)
• $i = 2$: Insert $y$ once (string becomes $xyyz$)
• $i = k$: Insert $y$ $k-1$ times (string becomes $xy^kz$)

How to Use the Pumping Lemma

Strategy for Proving Non-regularity

1. Assume $L$ is regular and let $p$ be its pumping length
2. Choose a string $s \in L$ with $|s| \geq p$ (carefully selected)
3. Consider all possible decompositions $s = xyz$ with $|xy| \leq p$ and $|y| > 0$
4. Show that for each decomposition, there exists some $i \geq 0$ such that $xy^iz \notin L$
5. Conclude that $L$ is not regular

Proof Structure

To prove $L$ is not regular:

Assume L is regular for contradiction
Let p be the pumping length
Choose s = (careful selection)
For all possible xyz decompositions:
    Find i such that xy^iz ∉ L
Therefore L is not regular

Common Examples

Example 1: $L = \{a^n b^n \mid n \geq 0\}$

Proof that $L$ is not regular:

1. Assume $L$ is regular with pumping length $p$
2. Choose $s = a^p b^p \in L$ (note $|s| = 2p \geq p$)
3. Consider any decomposition $s = xyz$ where $|xy| \leq p$ and $|y| > 0$
   • Since $|xy| \leq p$, $xy$ consists only of $a$'s
   • Let $y = a^k$ where $k \geq 1$
4. Pump with $i = 2$: $xy^2z = a^{p+k} b^p$
   • This has $p+k$ $a$'s but only $p$ $b$'s
   • Since $k \geq 1$, $p+k \neq p$
   • Therefore $a^{p+k} b^p \notin L$
5. Conclusion: $L$ is not regular

Example 2: $L = \{ww \mid w \in \{a, b\}^*\}$

Proof that $L$ is not regular:

1. Assume $L$ is regular with pumping length $p$
2. Choose $s = a^p b a^p b \in L$ (where $w = a^p b$)
3. Consider any decomposition $s = xyz$ with $|xy| \leq p$ and $|y| > 0$
   • $xy$ must be entirely within the first $a^p$ sequence
   • Let $y = a^k$ where $k \geq 1$
4. Pump with $i = 0$: $xz = a^{p-k} b a^p b$
   • This cannot be written as $ww$ for any $w$
   • The first half would need to be $a^{(p-k)/2} b$ but $(p-k)/2$ may not be integer
5. Conclusion: $L$ is not regular

Example 3: $L = \{a^{n^2} \mid n \geq 0\}$

Proof that $L$ is not regular:

1. Assume $L$ is regular with pumping length $p$
2. Choose $s = a^{p^2} \in L$
3. Consider decomposition $s = xyz$ with $|xy| \leq p$ and $|y| = k$ where $k \geq 1$
4. Pump with $i = 2$: $xy^2z = a^{p^2 + k}$
   • We need $p^2 + k = m^2$ for some integer $m$
   • But $p^2 < p^2 + k \leq p^2 + p < (p+1)^2 = p^2 + 2p + 1$
   • Since $k \leq p$, $p^2 + k$ cannot be a perfect square
5. Conclusion: $L$ is not regular

Example 4: $L = \{a^i b^j c^k \mid i = j \text{ or } j = k\}$

Proof that $L$ is not regular:

1. Assume $L$ is regular with pumping length $p$
2. Choose $s = a^p b^p c^{p+1} \in L$ (satisfies $i = j$)
3. Consider any decomposition $s = xyz$ with $|xy| \leq p$ and $|y| > 0$
   • Since $|xy| \leq p$, $y$ consists only of $a$'s
   • Let $y = a^k$ where $k \geq 1$
4. Pump with $i = 0$: $xz = a^{p-k} b^p c^{p+1}$
   • For this to be in $L$, we need either:
     • $p-k = p$ (impossible since $k \geq 1$), or
     • $p = p+1$ (impossible)
   • Therefore $xz \notin L$
5. Conclusion: $L$ is not regular

This example shows how the pumping lemma can handle languages with multiple conditions.

Common Mistakes and Pitfalls

Incorrect String Selection

Mistake: Choosing strings that are too short or don't create the right imbalance

Solution: Choose strings where the pumped part creates a clear violation

Wrong Pumping Index

Mistake: Always using $i = 2$ when $i = 0$ might be more effective

Solution: Consider different values of $i$ based on the language structure

Ignoring All Decompositions

Mistake: Only considering one specific decomposition

Solution: Must consider all possible decompositions satisfying the constraints

Variations and Extensions

Pumping Lemma for Context-Free Languages

The pumping lemma for context-free languages is more complex but follows a similar approach:

• Strings can be divided into five parts: $uvwxy$
• Two parts can be pumped independently

Ogden's Lemma

A stronger version that allows marking positions in the string to pump.

Practical Applications

Compiler Design

• Proving that certain language constructs cannot be handled by regular grammars
• Understanding limitations of lexical analysis

Formal Language Theory

• Classifying languages within the Chomsky hierarchy
• Understanding the boundaries of different language classes

Limitations

What the Pumping Lemma Cannot Do

1. Prove regularity: The lemma only provides a necessary condition, not sufficient
2. Give the pumping length: The lemma doesn't tell us what $p$ is
3. Handle all cases: Some non-regular languages may still satisfy the pumping lemma for certain pumping lengths

When the Pumping Lemma Fails

Some non-regular languages satisfy the pumping lemma:

• $L = \{a^n b^m c^n d^m \mid n, m \geq 0\}$ (not regular but satisfies pumping lemma for certain cases)

Summary

The Pumping Lemma is a powerful tool for proving that languages are not regular. By:

• Understanding the decomposition and pumping conditions
• Carefully selecting test strings
• Systematically analyzing all possible decompositions
• Choosing appropriate pumping indices

We can demonstrate that many interesting languages (like balanced parentheses, equal numbers of symbols, etc.) cannot be recognized by finite automata, highlighting the limitations of regular languages and motivating the study of more powerful language classes.

Remember that the Pumping Lemma is a proof by contradiction technique - we assume regularity and show that it leads to a contradiction by finding strings that cannot be pumped properly.

Problem-Solving Skills: Picking s and i

1. Analyze constraints of L

   • Identify the invariant that pumping will likely break (e.g., equal counts, mirrored halves, forbidden substrings at boundaries).

2. Choose s with |s| ≥ p

   • Place the first p symbols to force y within a controlled region (often a block of the same symbol).

3. Quantify all decompositions

   • Because |xy| ≤ p, y lies in the prefix you control; write y’s general form.

4. Pick i smartly

   • Use i=0 to delete structure or i=2 to increase a count; choose whichever breaks the invariant.

5. Conclude by contradiction

   • Show at least one i yields a string not in L for every legal decomposition.

Additional Worked Examples

L = { strings over {a,b} with exactly one b }

Assume regular, pumping length p. Choose s = a^p b a^p. For any |xy| ≤ p, y = a^k with k ≥ 1. Pump i=0 ⇒ a^{p-k} b a^p has still one b, but length of a’s changes. That alone doesn’t break the spec. Instead pump i=2 ⇒ a^{p+k} b a^p still exactly one b. This language is actually regular; pumping does not lead to a contradiction. Use this as a reminder to test closure intuition before applying pumping.

L = { w ∈ {0,1}^* | #0(w) = #1(w) }

Choose s = 0^p 1^p. y lies in 0^p, so y = 0^k, k ≥ 1. Pump i=2 ⇒ 0^{p+k}1p, counts differ ⇒ not in L.

L =

Choose s = a^p b a^p. y in leading a’s, y = a^k, k ≥ 1. Pump i=0 ⇒ a^{p-k} b a^p where head and tail a-counts differ ⇒ not in L.

Strategy Comparisons

Pumping Lemma:active

Use to prove non-regularity by contradiction.

Myhill–Nerode

Show infinitely many distinguishable prefixes/suffixes to prove no finite index, hence non-regular.

Closure Tricks

Transform with closures (complement, intersection, homomorphisms) to/from known non-regular languages.

Tips

If pumping seems messy, try Myhill–Nerode: fix a family of distinguishing continuations and show they separate infinitely many prefixes.

Changelog

9/7/25, 2:51 AM

View All Changelog

• 87c17-web-deploy(Auto): Update base URL for web-pages branchon 9/7/25

Copyright

Copyright Ownership:WARREN Y.F. LONG

License under:Attribution-NonCommercial-NoDerivatives 4.0 International (CC-BY-NC-ND-4.0)