Statement#

Use the Pumping Lemma for Regular Languages to prove that the language: $L = \{0^n1^n : n \geq 0\}$ is not regular.

Required Topics#

• Pumping lemma
• Regular languages
• Proof by contradiction
• String decomposition
• DFA limitations

The Pumping Lemma#

If $L$ is a regular language, then there exists a pumping length $p \geq 1$ such that:

For every string $s \in L$ with $|s| \geq p$, there exists a decomposition $s = xyz$ satisfying:

1. $|y| > 0$ (y is non-empty)
2. $|xy| \leq p$ (xy occurs within first p symbols)
3. For all $i \geq 0$: $xy^iz \in L$ (can pump y any number of times)

Proof Strategy#

1. Assume (for contradiction) that $L$ is regular
2. Apply the pumping lemma: there exists pumping length $p$
3. Choose a specific string $s \in L$ with $|s| \geq p$
4. Consider all possible decompositions $s = xyz$ satisfying conditions 1 and 2
5. Find some $i$ such that $xy^iz \notin L$
6. Conclude contradiction, so $L$ is not regular

Suggested String#

Choose $s = 0^p 1^p$ (clearly in $L$ and $|s| = 2p \geq p$).

What to Show#

1. Explain where $y$ must be located (hint: in the first $p$ symbols)
2. What does $y$ consist of? (only 0s, only 1s, or mixed?)
3. Find an $i$ such that $xy^iz$ has unequal numbers of 0s and 1s
4. Conclude $xy^iz \notin L$, contradicting the pumping lemma

Solution#

Solution coming soon.