# Pumping Lemma (for Regular Languages)

This section will be about languages that are *not* regular. You will see what a non-regular language looks like and how to formally prove that a language is not regular with the pumping lemma for regular languages. You will also see how to use the closure properties of regular languages to â€śquicklyâ€ť prove that languages are not regular. You can find the notes related to this section here.

#### Non-regular languages

What makes a language regular? Is there some characteristic that regular languages share that allows us to be able to write down DFAs for them? These are quite deep questions. I discuss some of the characteristics that differentiate regular and non-regular languages in the next video.

Part of the intuition of the pumping lemma is that the DFAs that accept regular languages must have some form of â€śrecycledâ€ť state. That is, if a language \(L\) is regular (and infinite), then the substrings that cycle through this recycled state can do so as many times as they want. Because the cycle is on a walk from the initial state to an accept state, any number of passes through the cycle will always lead to the string being accepted. This idea can be made more rigorous and is usually proved formally via the pigeonhole principle. In the next video, I present the lemma and break it up into (potentially) more digestible parts.

#### Using the PL to prove non-regularity

We know what the pumping lemma says, now how can we actually use it to prove that a language is not regular? I discuss using the negation of the pumping lemma to prove non-regularity *in the form of a game!*

Now letâ€™s play! I present a pumping lemma proof to show that \(\{a^nb^n : n \geq 0\}\) is not regular. An example that has been done to death, but that is excellent for presenting a first pumping lemma proof.

#### Using the closure properties to prove non-regularity

Youâ€™ll remember from the closure properties of regular languages that some operations are â€śregularâ€ť. That is, regular languages are closed under some operations. For instance, if \(A\) and \(B\) are two regular languages then \(A \cup B\) is also regular. This makes \(\cup\) a regular operation. Amazingly (and also very conveniently), the closure properties also allow us to prove that languages are not regular. More in the next video.

#### Exercises

**Exercise.**Prove that \(L = \{ 0^n 1^j, n > j \geq 0 \} \) is not regular.

**Exercise.**Prove that \(L = \{a^n : n = k^3\}\) is not regular.

**Exercise.**Is the language \(L=\{a^nb^l:n/l\in Z\}\) regular? Prove your claim.

**Exercise.**Is the language \(L=\{w \in \{a,b\}^* : n_a(w) + n_b(w) = 4n_b(w) \}\) regular? Prove your claim.

**Exercise.**Is the language \(L = \{a^{2n} : n \geq 0\} \cup \{a^{2^n} : n \geq 0 \}\) regular? Prove your claim.

**Exercise.**Let \(L = \{a^nb^kc^{n+k}d^p : n,k,p \geq 0\} \) be a language we are trying to show is not regular using the pumping lemma. Suppose your opponent chooses an integer \(m > 0 \). Which of the following strings for \(w \) would be a suitable choice to show that \(L \) is not regular? Should you pump up or pump down?

- \(w = a^mb^mc^m \)
- \(w = a^mb^m \)
- \(w = a^mc^m \)
- \(w = a^mb^{2m}c^md^m \)

**Exercise.**Show that you cannot use the pumping lemma to prove that \(L = \{a^ib^jc^k : i = 0 \implies j = k\}\) is not regular.

**Exercise.**Prove that \(L=\{w\in \Sigma ^*: w \text{ has more 0's than 1's} \}\) is not regular.

**Exercise.**Use the closure properties of regular languages to prove that \(L=\{ a^n b^n: n\geq 335\}\) is not regular.

**Exercise.**Is the language \(L = \{w_1cw_2 : w_1,w_2 \in \{a,b\}^*, w_1 \neq w_2\}\) regular? Prove your answer.