How can we prove that a language is not regular?

Overview of pumping lemma

A well defined theorem called the pumping lemma has been formed to check the non-regularity of a programming language. However, this lemma doesn't show if a language is regular. Some other simple techniques can also be used to check the non-regularity of a language.

Pumping lemma

Pumping lemma states that for any regular language $L$, there exists an integer $n$, in a way that for all $x ∈ L$ with $|x| ≥ n$, there exists $u, v, w ∈ Σ^∗$ such that:

1. $|uv|≤ n$
2. $|v|≥ 1$
3. $for \space all \space i ≥ 0: uv^iw$

These given rules mean that if a particular string of a language is pumped, that is, if a part v of the string is repeated i number of times, it still remains a part of the language.

How lemma works

The lemma gives a result in the form of a contradiction. We suppose that a given instance (string) of a language is regular, and we contradict our supposition because the pumped string will not be a part of the language.

Examples

Let's look at an example of this:

Let $L = \{0^n1^n : n ∈ N\}$ and suppose L is a regular language.

Take $x = 0^n1^n$ where $|x|= 2n > n$ and $x ∈ L$

We divide x in such a way that $uv = 0^n$ where $|uv|≤ n (u = 0^{n/2} \space and \space v = 0^{n/2}) \space and \space w = 1^n$.

Taking i = 0: $uv^iw = (0^{n/2}) (0^{n/2})^0 (1^n)$

     $= 0^{n/2} 1^n ∉ L$

Since the string is not a part of the language, we can say that our initial supposition is wrong and that the language $L$ is non-regular.

Let's look at another example:

$L = {a^i b^j c^k : i, j, k > 0 \space and \space i < j < k}$ and suppose $L$ is a regular language.

$x = a^n b^{n+1} c^{n+2}$ where $|x| = 3n+3 > n$ and $x ∈ L$ and is part of a regular language.

Taking $uv = a^n$ where $|uv|≤ n ( u = a^{n-k} \space and \space v = a^k ) \space and \space w = (b^{n+1}c^{n+2})$

Taking i = 2:

  $uv^iw = (a^{n-k})(a^k )^2 (b^{n+1}c^{n+2})$

     $= a^{n-k+2k} (b^{n+1}c^{n+2})$

$= a^{n+3k} (b^{n+1}c^{n+2}) ∉ L$ as $i > j$

Again, we see that the string is not a part of the language, so we can say that our initial supposition is wrong and that the language $L$ is non-regular.

Other techniques

1. If there is no pattern present to make all the strings of a language, then that language is non-regular.

  e.g. $L = {x^y \space where\space y \space is\space prime}$

2. If a language forms a geometric progression, then it's a non-regular language.

  e.g. $L = {a^{2^n} : n ≥ 1}$

3. An infinite set of elements always make up a non-regular language.

  e.g. $L = All \space strings \space in \space \{0,1\}^*$