Trusted answers to developer questions

Zainab Ilyas

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 states that for any regular language

$|uv|≤ n$ $|v|≥ 1$ -
$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.

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.

Let's look at an example of this:

Let** **

Take ^{ }where

We divide x in such a way that

Taking i = 0:

Since the string is not a part of the language, we can say that our initial supposition is wrong and that the language

Let's look at another example:

^{ }^{ }where

Taking

Taking i = 2:

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

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

e.g.

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

e.g.

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

e.g.

RELATED TAGS

pumping lemma

regular languages

CONTRIBUTOR

Zainab Ilyas

RELATED COURSES

View all Courses

Keep Exploring

Related Courses