Proving Non-Regularity with the Pumping Lemma

1. The Proof by Contradiction Game Plan

To prove a language $L$ is not regular, we use proof by contradiction. The Pumping Lemma provides the perfect framework for this. Think of it as a game where you must show that the rules of the lemma can be broken for language $L$.

Here is the game plan, which will be our template for every proof:

1. Your Assumption: Assume, for the sake of contradiction, that $L$ is regular.
2. Adversary's Move (The Lemma's Guarantee): Because $L$ is assumed regular, the Pumping Lemma must apply. The lemma guarantees that there exists a pumping length $p$ for $L$. This $p$ is a specific integer, but we don't know its value—we just know it exists.
3. Your Move (Strategic String Selection): You choose a specific string $w$ that is in $L$ and has a length of at least $p$ ($|w|\ge p$). The success of the proof hinges on choosing a clever $w$ that exploits the structural weakness of the language.
4. Adversary's Second Move (The Decomposition): The lemma guarantees that your chosen string $w$ can be divided into three parts, $w=xyz$, satisfying three conditions:
   • (1) $|y|>0$ (The pumpable part is not empty).
   • (2) $|xy|\le p$ (The pumpable part occurs early in the string).
   • (3) For all $i\ge 0$, the string $x{y}^{i}z$ is in $L$ (You can pump $y$ and the result stays in the language).
     You don't get to choose how $w$ is split, but you know that however it's split, these three conditions must hold.
5. Your Winning Move (Finding the Contradiction): You must show that for any possible way the adversary splits $w$ into $xyz$ (while respecting the conditions), you can find a value for $i$ (usually 0 or 2) such that the pumped string $x{y}^{i}z$ is not in $L$.
6. Checkmate: This contradicts condition (3) of the lemma. Since the Pumping Lemma's guarantee is broken, the only thing that could have been wrong was our initial assumption. Therefore, $L$ cannot be regular.

This adversarial framework is essential. Your proof must be robust enough to work no matter which valid decomposition the "adversary" (the lemma) provides.

2. Proof: $L=\{a^n{b}^n\mid n\ge 0\}$ is Not Regular

Let's apply our game plan to prove that the language of strings with some number of $a$'s followed by the same number of $b$'s is not regular. This is a canonical example because it captures the idea of "counting," which finite automata struggle with.

The following video provides a clear, step-by-step walkthrough of this exact proof. Watch how the presenter follows the logical structure we just outlined.

Now, let's formalize the steps from the video in writing:

1. Assumption: Assume $L=\{a^n{b}^n\mid n\ge 0\}$ is a regular language.

2. Pumping Length: By the Pumping Lemma, there must exist a pumping length $p$ for $L$.

3. String Selection: We choose the string $w=a^p{b}^p$. This string is in $L$ (with $n=p$), and its length is $2p$, which is $\ge p$. This is a strategic choice because the number of $a$'s and $b$'s is tied to the pumping length $p$.

4. Decomposition: According to the Pumping Lemma, $w$ can be split into $xyz$ such that:

   • $|y|>0$
   • $|xy|\le p$
   • For all $i\ge 0$, $x{y}^{i}z\in L$

5. Case Analysis: Let's analyze what $x,y,$ and $z$ must look like.

   • Our string is $w=\underset{p\text{ times}}{\underbrace{aaa\dots a}}\underset{p\text{ times}}{\underbrace{bbb\dots b}}$.
   • The condition $|xy|\le p$ forces the substring $xy$ to be located within the first $p$ characters of $w$.
   • The first $p$ characters of $w$ are all $a$'s.
   • Therefore, both $x$ and $y$ must consist entirely of $a$'s.
   • Furthermore, the condition $|y|>0$ tells us that $y$ contains at least one $a$. So, we can say $y=a^k$ for some integer $k\ge 1$.

6. Pumping and Contradiction: Let's choose $i=2$ and analyze the resulting string $w^{\prime }=x{y}^{2}z$.

   • The original string $w=xyz$ had $p$ $a$'s and $p$ $b$'s.
   • The new string $w^{\prime }=xyyz$ contains a second copy of $y$. Since $y=a^k$ where $k\ge 1$, we have added $k$ extra $a$'s.
   • The number of $a$'s in $w^{\prime }$ is $p+k$.
   • The number of $b$'s is unchanged, so there are still $p$ $b$'s.
   • The resulting string is $a^{p+k}{b}^p$. Since $k\ge 1$, $p+k\ne p$.
   • This string is not in $L$ because the number of $a$'s and $b$'s is no longer equal.

7. Conclusion: This is a contradiction. The Pumping Lemma guaranteed that $x{y}^{i}z$ would be in $L$ for any $i$, but we showed that for $i=2$, it is not. Our initial assumption must be false. Therefore, $L=\{a^n{b}^n\mid n\ge 0\}$ is not regular.

3. A Second Example: $L=\{ww\mid w\in \{0,1{\}}^{\ast }\}$

The proof structure is a recipe. To solidify your understanding, let's apply it to another language: the language of strings that consist of some non-empty string repeated twice. For example, 0101 is in $L$ (where $w=01$), but 0110 is not.

Your experience with algorithms and data structures makes it clear that checking for this property likely requires memory to store the first half (w) and compare it against the second half—something a finite automaton cannot do. Let's prove this formally.

As Professor Sipser explains, the choice of string is crucial.

• A naive choice like $s=0^{2p}$ (i.e., $w=0^p$) fails. The string is $0^p{0}^p$. If we pump a section $y=0^k$ within the first half, the resulting string is still just a long string of zeros, which can be seen as $0^j{0}^j$ for some new $j$, so it's still in $L$. No contradiction is reached.
• A strategic choice is needed, one that breaks if we modify just one part. The choice $s=0^{p}10^{p}1$ is excellent. Here, $w=0^{p}1$.

Let's complete the proof for $L=\{ww\mid w\in \{0,1{\}}^{\ast }\}$ using $s=0^{p}10^{p}1$:

1. Assumption: Assume $L$ is regular.
2. Pumping Length: Let $p$ be the pumping length.
3. String Selection: Choose $s=0^{p}10^{p}1$. This string is in $L$ and $|s|=2p+2\ge p$.
4. Decomposition: $s$ can be split into $xyz$ with $|y|>0$ and $|xy|\le p$.
5. Case Analysis:
   • The string is $\underset{p\text{ times}}{\underbrace{00\dots 0}}1\underset{p\text{ times}}{\underbrace{00\dots 0}}1$.
   • Since $|xy|\le p$, the substring $xy$ must fall entirely within the initial block of $p$ zeros.
   • Therefore, $y$ must be a non-empty string of zeros: $y=0^k$ for some $k\ge 1$.
6. Pumping and Contradiction: Let's pump with $i=2$, creating $s^{\prime }=x{y}^{2}z$.
   • We are adding $k$ zeros to the first block of zeros. The rest of the string is unchanged.
   • $s^{\prime }=0^{p+k}10^{p}1$.
   • This string is no longer of the form $ww$. The first half up to the middle is $0^{p+k}1$, but the second half is $0^{p}1$. These are not equal. Thus, $s^{\prime }\notin L$.
7. Conclusion: We have a contradiction. Therefore, $L=\{ww\mid w\in \{0,1{\}}^{\ast }\}$ is not regular.

For a concise written version of these proofs, you can refer to the following lecture notes.

Conclusion

Today, we put the Pumping Lemma to work. We've established a robust, reusable framework for proving that a language is not regular. This method is a cornerstone of automata theory, providing a formal way to identify the limitations of finite-state machines.

Key Takeaways:

• Proofs of non-regularity using the Pumping Lemma are structured as a proof by contradiction.
• The process can be viewed as an adversarial game where you must show that for a strategically chosen string, any valid decomposition according to the lemma's rules can be "pumped" out of the language.
• The two most powerful constraints you have are:
  1. Your choice of the string $w$. It should be chosen to create a dependency (like counting) that is tied to the pumping length $p$.
  2. The lemma's condition that $|xy|\le p$, which severely restricts where the pumpable section $y$ can be located.
• We successfully applied this framework to prove that $L=\{a^n{b}^n\mid n\ge 0\}$ and $L=\{ww\mid w\in \{0,1{\}}^{\ast }\}$ are not regular.

Preview of the Next Lesson:
Now that we have a tool to identify non-regular languages, we will turn our attention to the properties of the languages we know are regular. In the next lesson, we will explore the closure properties of regular languages. We will prove that if you take regular languages and apply operations like union, intersection, or complement, the result is still a regular language. This will give us another powerful set of tools for reasoning about languages and their complexity.