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 \)
No solution for this one yet!
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.
The idea here is to show that \(L\) does in fact satisfy the conditions of the PL.
Recall what the PL says
$$\exists m > 0 . \forall w \in L, |w| \geq m . \exists w = xyz, |xy| \leq m, |y| \geq 1 . \forall i \geq 0, xy^iz \in L$$
We fix some \(m > 0\). Now we must consider all possible strings \(w \in L\) with length greater or equal to \(m\). We break this up into cases which will be based off the number of \(a\)'s in \(w\).
We have the following cases:
\(w\) has no \(a\)'s. In this case, \(w\) has the form \(b^jc^k\) where \(j + k \geq m\). If \(j \geq 1\), we select \(y = b\). Then for any pump of this string \(xy^iz\) will clearly still be in \(L\). If \(j = 0\), then set \(y = c\). Any pump of this string will again remain in \(L\).
\(w = ab^nc^n, 2n + 1 \geq m\). We can pick \(y = a\) and we will have \(xy^iz \in L, \forall i\). This is the key: to notice that if \(i = 1\) implies the number of \(b\)'s and \(c\)'s must be equal but nothing says that the number of \(b\)'s and \(c\)'s can't be equal even if \(i \neq 1\).
\(w\) has more than 1 \(a\). In this case, we need to be more careful. We mustn't pick a \(y\) that, when pumped down, will create the string \(xy^iz = a b^j c^k, j \neq k \). To do so, we set \(y\) to the entire sequence of \(a\)'s if there are \(m\) of fewer \(a\)'s in \(w\). Otherwise, we set it to \(a^{m-1}\) (so that the gap is of at least 2 \(a\)'s).
This shows that \(L\) satisfies the conditions of the PL. Therefore, even though we know it isn't regular (use the closure properties!), we cannot prove this with the pumping lemma. We will see that the Myhill-Nerode theorem can help us with this limitation.
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.