---
title: "Pumping lemma: equal 0s and 1s"
subject: "Theory of Computation"
chapter: 2
key: "semester_3/theory_of_computation:pumping-equal-zeros-ones"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/pumping-equal-zeros-ones
site: BCT Engineering
---

# Pumping lemma: equal 0s and 1s

Theory of Computation · Chapter 2: Finite Automata

- Asked in: 2073 Chaitra
- Video: [Pumping Lemma for Regular Languages Example: 0ⁿ1ⁿ](https://www.youtube.com/watch?v=vcND4aGPWtM) — Easy Theory
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/pumping-equal-zeros-ones
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-2

## Question

State the pumping lemma for regular languages. Using the pumping lemma, prove that the language L = {w : w ∈ {0,1}* and w has an equal number of 0's and 1's} is not regular.

## Short answer

If L is regular, there exists p≥1 such that any w∈L with |w|≥p can be split w=xyz, |xy|≤p, |y|≥1, xyⁱz∈L for all i. Assume L={w∈{0,1}* | equal 0 and 1} regular with p, take w=0^p 1^p. Since |xy|≤p, y=0^k (k≥1). Pump i=2 yields 0^(p+k)1^p, unequal counts, not in L, contradiction, so L not regular.

## Answer

#### Pumping lemma
If L is regular, there is p ≥ 1 such that every w ∈ L with |w| ≥ p can be split w = xyz where |xy| ≤ p, |y| ≥ 1 and xyⁱz ∈ L for all i ≥ 0.

#### Proof that L = {w ∈ {0,1}* : #0(w) = #1(w)} is not regular
Assume L is regular with pumping length p.

1. Choose w = 0ᵖ1ᵖ. It has p zeros and p ones, so w ∈ L, and |w| = 2p ≥ p.
2. Since |xy| ≤ p, the substring xy lies in the block of 0's. So y = 0ᵏ with 1 ≤ k ≤ p.
3. Take i = 2: xy²z = 0^(p+k)1ᵖ.
4. It has p + k zeros but only p ones, and k ≥ 1, so the counts are unequal. Therefore xy²z ∉ L.

This contradicts the pumping lemma, so L is **not regular**. ∎

**Alternative proof (closure).** If L were regular, then L ∩ 0*1* would be regular (regular languages are closed under intersection). But L ∩ 0*1* = {0ⁿ1ⁿ : n ≥ 0}, which is known to be non-regular. Contradiction.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. Which string is used for equal numbers of 0s and 1s?
   A. 1^p 0^p 1
   B. 0^p 1^p
   C. 0^p 1^(p+1)
   D. (01)^p
   Answer: B. It is in L and forces y into the 0s. (Key point: String choice)

2. Why is y = 0^k?
   A. Because y must have equal 0s and 1s
   B. Because z is all 1s
   C. Because x is empty
   D. |xy| ≤ p lies inside the leading block of 0s
   Answer: D. The first p symbols are all 0. (Key point: Form of y)

3. After i = 2 we get 0^(p+k)1^p. Why is it not in L?
   A. It is shorter than w
   B. It has equal counts
   C. It has p+k zeros but p ones, and k ≥ 1
   D. It has no zeros
   Answer: C. Counts unequal, so xy^2z ∉ L. (Key point: Contradiction)

4. How does the closure-based proof go?
   A. Intersect L with 0*1* to get {0^n 1^n}, known non-regular
   B. Concatenate L with 0*
   C. Take the Kleene star of L
   D. Complement L to get a finite language
   Answer: A. Regular languages are closed under intersection, so L regular would make 0^n1^n regular. (Key point: Alternative proof)

## Close variants set in other exams

- [Pumping lemma: a^(n²) not regular](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apumping-square-not-regular) — Theory of Computation, chapter 2, asked 5×

## Related in Theory of Computation

- [Pumping lemma: aⁿb²ⁿ not regular](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apumping-an-b2n-not-regular) — Theory of Computation, chapter 2, asked 3×
- [Pumping lemma: aⁿbaⁿ not regular](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apumping-anban-not-regular) — Theory of Computation, chapter 2
- [Pumping lemma (CFL): ww not CF](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apumping-cfl-ww) — Theory of Computation, chapter 3
- [Pumping lemma: a^p, p prime](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apumping-prime-not-regular) — Theory of Computation, chapter 2, asked 2×
- [Pumping lemma (CFL): aⁿbⁿcⁿ not CF](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apumping-cfl-an-bn-cn) — Theory of Computation, chapter 3
- [Closure properties of regular languages](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Aregular-closure-properties) — Theory of Computation, chapter 2, asked 2×

## Related in other subjects

- [Regular expressions and regular languages](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Aregular-expressions-and-languages) — Discrete Structure, chapter 2
- [Closure properties of regular languages](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Aclosure-properties-regular-language) — Discrete Structure, chapter 2, asked 2×
- [High level languages and natural language](https://www.bctengineer.com/question.md?key=semester_1%2Fcomputer_programming%3Ahll-similar-natural-language) — Computer Programming, chapter 1