# How to prove that a language is not regular?

We learned about the class of regular languages $\mathrm{REG}$. It is characterised by any one concept among regular expressions, finite automata and left-linear grammars, so it is easy to show that a given language is regular.

How do I show the opposite, though? My TA has been adamant that in order to do so, we would have to show for all regular expressions (or for all finite automata, or for all left-linear grammars) that they can not describe the language at hand. This seems like a big task!

I have read about some pumping lemma but it looks really complicated.

This is intended to be a reference question collecting usual proof methods and application examples. See here for the same question on context-free languages.

-

Proof by contradiction is often used to show that a language is not regular: let $P$ a property true for all regular languages, if your specific language does not verify $P$, then it's not regular. The following properties can be used:

1. The pumping lemma, as exemplified in Dave's answer;
2. Closure properties of regular languages (set operations, concatenation, Kleene star, mirror, homomorphisms);
3. A regular language has a finite number of prefix equivalence class, Myhill–Nerode theorem.

To prove that a language $L$ is not regular using closure properties, the technique is to combine $L$ with regular languages by operations that preserve regularity in order to obtain a language known to be not regular, e.g., the archetypical language $I= \{ a^n b^n | n \in \mathbb{N} \}$. For instance, let $L= \{a^p b^q | p \neq q \}$. Assume $L$ is regular, as regular languages are closed under complementation so is $L$'s complement $L^c$. Now take the intersection of $L^c$ and $a^\star b^\star$ which is regular, we obtain $I$ which is not regular.

The Myhill–Nerode theorem can be used to prove that $I$ is not regular. For $p \geq 0$, $I/a^p= \{ a^{r}b^rb^p| r \in \mathbb{N} \}=I.\{b^p\}$. All classes are different and there is a countable infinity of such classes. As a regular language must have a finite number of classes $I$ is not regular.

-
Didn't know about Myhill-Nerode theorem, cool! – Daniil Apr 4 '12 at 13:20
Wikipedia also has a section about the number of words in a regular language: if you can prove your language doesn't match the characterization, then your language is not regular: en.wikipedia.org/wiki/… – Alex ten Brink Apr 4 '12 at 14:39
@Daniil, regular expressions can't count seems to me a popular informal formulation of Myhill-Nerode theorem. – AProgrammer Apr 4 '12 at 15:28
@AlextenBrink: That is neat. I guess the constants in the statement are the eigenvalues of the automaton's Laplacian? This would make a nice addition to the answers here. – Louis Apr 4 '12 at 20:27
@Louis: actually, we've found no reference for that theorem at all, so if you know more about it... Also see: cs.stackexchange.com/questions/1045/… – Alex ten Brink Apr 4 '12 at 20:31

From Wikipedia, the pumping language for regular languages is the following:

Let $L$ be a regular language. Then there exists an integer $p\ge 1$ (depending only on $L$) such that every string $w$ in $L$ of length at least $p$ ($p$ is called the "pumping length") can be written as $w = xyz$ (i.e., $w$ can be divided into three substrings), satisfying the following conditions:

1. $|y| \ge 1$
2. $|xy| \le p$ and
3. for all $i \ge 0$, $xy^iz \in L$.
$y$ is the substring that can be pumped (removed or repeated any number of times, and the resulting string is always in $L$).

(1) means the loop y to be pumped must be of length at least one; (2) means the loop must occur within the first p characters. There is no restriction on x and z.

In simple words, For any regular language L, any sufficiently long word $w\in L$ can be split into 3 parts. i.e $w = xyz$, such that all the strings $xy^kz$ for $k\ge 0$ are also in $L$.

Now let's consider an example. Let $L=\{(01)^n2^n\mid n\ge0\}$.

To show that this is not regular, you need to consider what all the decompositions $w=xyz$ look like, so what are all the possible things x, y and z can be given that $xyz=(01)^p2^p$ (we choose to look at this particular word, of length $3p$, where $p$ is the pumping length). We need to consider where the $y$ part of the string occurs. It could overlap with the first part, and will thus equal either $(01)^{k+1}$, $(10)^{k+1}$, $1(01)^k$ or $0(10)^k$, for some $k\ge 0$ (don't forget that $|y|\ge 1$). It could overlap with the second part, meaning that $y=2^k$, for some $k>0$. Or it could overlap across the two parts of the word, and will have the form $(01)^{k+1} 2^l$, $(10)^{k+1} 2^l$, $1(01)^k 2^l$ or $0(10)^k 2^l$, for $k\ge0$ and $l\ge1$.

Now pump each one to obtain a contradiction, which will be a word not in your language. For example, if we take $y=0(10)^k2^l$, the pumping lemma says, for instance, that $xy^2z=x0(10)^k2^l0(10)^k2^lz$ must be in the language, for an appropriate choice of $x$ and $z$. But this word cannot be in the language as a $2$ appears before a $1$.

Other cases will result in the number of $(01)$'s being more than the number of $2$'s or vice versa, or will result in words that won't have the structure $(01)^n2^n$ by, for example, having two $0$'s in a row.

Don't forget that $|xy| \le p$. Here, it's useful to shorten the proof: many of the decompositions above are impossible because they would make the $z$ part too long.

Each of the cases above needs to lead to such a contradiction, which would then be a contradiction of the pumping lemma. Voila! The language would not be regular.

-
An example where the hypothesis $|xy|\le p$ is needed would be nice. – Gilles Apr 4 '12 at 15:25
@Gilles: I'm not even sure what the sentence you added means. – Dave Clarke Apr 4 '12 at 15:28
@Gilles: I think that all the decompositions are possible, just that $k$ will be bounded. I'm not sure what it has to do with the length of $z$. – Dave Clarke Apr 4 '12 at 15:32
Duh! I see it now. Thanks. It does not, however, rule out any of the forms of decomposition mentioned in the answer; it only limits what values of $k$ and $l$ I can take. – Dave Clarke Apr 4 '12 at 16:19
The amount of editing that has been done to answer such an easy question makes me wonder why everybody teaches the pumping lemma as "the" way to prove non-regularity. Out of curiosity, why not just take your string to be something like $(01)^{2p}2^{2p}$? The pumping lemma tells you that $y$ has no $2$s in it, from which a contradiction is more straightforward. – Louis Apr 4 '12 at 19:47

Based on Dave's answer, here is a step-by-step "manual" for using the pumping lemma.

Recall the pumping lemma (taken from Dave's answer, taken form Wikipedia):

Let $L$ be a regular language. Then there exists an integer $n\ge 1$ (depending only on $L$) such that every string $w$ in $L$ of length at least $n$ ($p$ is called the "pumping length") can be written as $w = xyz$ (i.e., $w$ can be divided into three substrings), satisfying the following conditions:

1. $|y| \ge 1$
2. $|xy| \le n$ and
3. a "pumped" $w$ is still in $L$: for all $i \ge 0$, $xy^iz \in L$.

Assume that you are given some language $L$ and you want to show that it is not regular via the pumping lemma. The proof looks like this:

1. Assume that $L$ is regular.
2. If it is regular, then the pumping lemma says that there exists some number $n$ which is the pumping length.
3. Pick a specific word $w\in L$ of length larger than $n$. The difficult part is to know which word to take.
4. Consider ALL the ways to partition $w$ into 3 parts, $w=xyz$, with $|xy|\le n$ and $y$ non empty. For each of these ways, show that it cannot be pumped: there always exists some $i\ge 0$ such that $xy^iz \notin L$.
5. Conclude: the word $w$ cannot be "pumped" (no matter how we split it to $xyz$) in contradiction to the pumping lemma, i.e., our assumption (step 1) is wrong: $L$ is not regular.

Before we go to an example, let me reiterate Step 3 and Step 4 (this is where most of the people go wrong). In Step 3 you need to pick one specific word in $L$. write it down explicitly, like "00001111" or "$a^nb^n$". Examples for things that are not a specific word: "$w$" or "a word that has 000 as a prefix".

On the other hand, in Step 4 you need to consider more than one case. For instance, if $w=000111$ it is not enough to say $x=00, y=01, z=00$, and then reach a contrudiction. You must also check $x=0, y=0, z=0111$, and $x=\epsilon, y=000, z=111$, and all the other possible options.

Now let's follow the steps and prove that $L= \{ 0^k1^{2k} \mid k>0 \}$ is not regular.

1. Assume $L$ is regular.
2. Let $n$ be the pumping length given by the pumping lemma.
3. Let $w = 0^n 1^{2n}$.
(sanity check: $|w|\gt n$ as needed. Why this word? other words can work as well.. it takes some experience to come up with the right $w$). Again, note that $w$ is a specific word: $\underbrace{000\ldots0}_{n \text{ times}}\underbrace{111\ldots1}_{2n \text{ times}}$.
4. Now lets start consider the various cases to split $w$ into $xyz$ with $|xy|\le n$ and $|y|>0$. Since $|xy|<n$ no matter how we split $w$, $x$ will consist of only 0's and so will $y$. Lets assume $|x|=s$ and $|y|=k$. We need to consider ALL the options, that is all the possible $s,k$ such that $s\ge 0, k\ge 1$ and $s+k \le n$. FOR THIS $L$ the proof for all these cases is the same, but in general it might be different.
take $i=0$ and consider $xy^iz = xz$. this word is NOT in $L$ since it is of the form $0^{n-k}1^{2n}$ (no matter what $s$ and $k$ were), and since $k \ge 1$, this word is not in $L$ and we reach a contradiction.
5. Thus, our assumption is incorrect, and $L$ is not regular.

A youtube clip that explains how to use the pumping lemma along the same lines can be found here

-
It's n that is the pumping length in this definition! – saadtaame Aug 24 '12 at 1:17

For a given language $L \subseteq \Sigma^*$, let

$\qquad \displaystyle S_L(z) = \sum\limits_{n \geq 0} |L \cap \Sigma^n|\cdot z^n$

the (ordinary) generating function of $L$, i.e. its sequence of word counts per length.

The following statement holds [FlSe09, p52]:

$\qquad \displaystyle L \in \mathrm{REG} \quad \Longrightarrow \quad S_L \text{ rational}$

That is, $S_L(z) = \frac{P(z)}{Q(z)}$ with $P,Q$ polynomials.

So any language whose generating function is not rational is not regular. Unfortunately, all linear languages also have rational generating functions¹ so this method won't work for the simpler non-regular languages. Another drawback is that obtaining $S_L$ (and showing that it is not rational) can be hard.

Example: Consider the language of correctly nested parentheses words, i.e. the Dyck language. It is generated by the unambiguous grammar

$\qquad \displaystyle S \to [S]S \mid \varepsilon$

which can be translated into the equation

$\qquad \displaystyle S(z) = z^2S^2(z) + 1$

one solution (the one with all positive coefficients) of which is

$\qquad \displaystyle \mathcal{S}(z) = \frac{1 - \sqrt{1 - 4z^2}}{2z^2}$.

As $S_L = \mathcal{S}$ [Kuic70] and $\mathcal{S}$ is not rational, the Dyck language is not regular.

1. The proof for the statement for regular languages works via grammars and transfers to linear grammars immediately (commutativity of multiplication).

$\ \$ [FlSe09] Analytic Combinatorics by P. Flajolet and R. Sedgewick (2009)
$\ \$ [Kuic70] On the Entropy of Context-Free Languages by W. Kuich (1970)

-

This is an expanded version of my answer from here Using Pumping Lemma to prove language is not regular since this is supposed to be a reference question.

So, you think the pumping lemma looks complicated? Don't worry. Here's a slightly different take approach, which is hidden in @Romuald's answer as well. (Quiz: where?)

Let's start by remembering that every regular language is accepted by a deterministic finite state automaton (DFA). A DFA is a finite directed graph where every vertex has exactly one out-edge for each letter in the alphabet. Strings give you a walk in the graph based at a vertex labeled "start", and the DFA accepts if this walk ends at a vertex labeled "accept". (The vertices are called "states" because different areas of math like to make up their own terminology for the same thing.)

With this way of thinking it is easy to see that: If strings $a$ and $b$ drive the DFA to the same state, then for any other string $c$, $ac$ and $bc$ drive the DFA to the same state. Why? Because the stating point of a walk and the string defining it determine the end completely.

Put slightly differently: If $L$ is regular and strings $a$ and $b$ drive a recognizing automaton to the same state, then for all strings $c$, either $ac$ and $bc$ are both in $L$ or neither is.

We can use this to show languages aren't regular by imagining it is and then coming up with $a$ and $b$ driving an DFA to the same state, and $c$ so that $ac$ is in the language and $bc$ isn't. Take the example language from @Dave's answer. Imagine it is regular, so it has some recognizing DFA with $m$ states. The Pigeon Hole Principle says that at least two of $\{(01)^i : 0\le i\le m+1\}$ send the DFA to the same state, say $a=(01)^p$ and $b=(01)^q$. Since $p\neq q$, we see that $a2^p$ is in the language and $b2^p$ is not, so this language can't be regular.

The nice thing is that the example is really a template for proving that languages aren't regular:

• Find a family of strings $\{a_i :i\in\mathbb{N}\}$ with the property that each of them has a "tail" $t_i$ so that $a_it_i$ is in the language and $a_it_j$, for $i\neq j$ is not.
• Apply the argument above verbatim. (This is allowed, since there are always enough $a_i$ to let you invoke the Pigeon Hole Principle.)

There are other tricks, but this one will work easily on most of your homework problems.

Edit: An earlier version had some discussion of how this idea relates to the Pumping Lemma.

-
I don't think that reproducing the proof of Pumping Lemma is useful in general, but YMMV. Understanding the proof is good in any case; it is immediately connected with a number of closure and other interesting properties of finite automata and regular languages. I strongly disagree with the last sentence, though: automata theory is not boring at all, and it is certainly not the most boring part of theory classes. – Raphael Apr 6 '12 at 11:27