Menu

© 2025 369 Tesla Private Limited

All Rights Reserved

Pumping Lemma Tool

Learn to prove languages are NOT in specific classes using pumping lemmas

Pumping Lemma Interactive Tool

Learn to prove languages are NOT in specific classes using pumping lemmas

Pumping Lemma Interactive Tool 🔄

Learn to prove languages are NOT in specific classes using pumping lemmas

Select Language Class

Pumping Lemma for Regular Languages

If L is regular, then ∃p ≥ 1 such that ∀w ∈ L with |w| ≥ p, ∃x,y,z with w = xyz where:

1. |xy| ≤ p
2. |y| ≥ 1
3. ∀i ≥ 0: xy^i z ∈ L

Select Language to Analyze

Interactive Proof: L = {aⁿbⁿ | n ≥ 0}

Step 1 of 7
Pumping Length p = 3

1Assume L is Regular

Assume L = {aⁿbⁿ | n ≥ 0} is regular. Then by the pumping lemma for regular languages, there exists a pumping length p ≥ 1.

Strings in L

"ab"
"aabb"
"aaabbb"
"aaaabbbb"

Strings NOT in L

"aab"
"abb"
"aaabb"
"aabbb"

Pumping Lemma Strategy

1

Assume

Language is in the class

2

Choose

Strategic string w ∈ L

3

Pump

Apply pumping lemma

4

Contradict

Show pumped string ∉ L

Key Tips:

String Choice: Pick strings that expose the language's structure

Pumping Strategy: Usually pump up (i > 1) or down (i = 0)

Constraints: Use length and position constraints effectively

Contradiction: Show the pumped string violates language definition