Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

pumping lemma
regular languages

How can we prove that a language is not regular?

Zainab Ilyas

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 LL, there exists an integer nn, in a way that for all xLx ∈ L with xn|x| ≥ n, there exists u,v,wΣu, v, w ∈ Σ^∗ such that:

  1. uvn|uv|≤ n
  2. v1|v|≥ 1
  3. for all i0:uviwfor \space all \space i ≥ 0: uv^iw
1 of 3

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={0n1n:nN}L = \{0^n1^n : n ∈ N\} and suppose L is a regular language.

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

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

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

     =0n/21nL= 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 LL is non-regular.

Let's look at another example:

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

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

Taking uv=anuv = a^n where uvn(u=ank and v=ak) and w=(bn+1cn+2)|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:

  uviw=(ank)(ak)2(bn+1cn+2)uv^iw = (a^{n-k})(a^k )^2 (b^{n+1}c^{n+2})

     =ank+2k(bn+1cn+2)= a^{n-k+2k} (b^{n+1}c^{n+2})

=an+3k(bn+1cn+2)L= a^{n+3k} (b^{n+1}c^{n+2}) ∉ L as i>ji > 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 LL 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=xy where y is primeL = {x^y \space where\space y \space is\space prime}

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

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

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

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

RELATED TAGS

pumping lemma
regular languages
RELATED COURSES

View all Courses

Keep Exploring