# Pumping Lemma for Regular Languages - Automata

**Pumping Lemma for Regular Languages**

The language accepted by the finite automata is called **Regular Language**. If we are given a language** L** and asked whether it is regular or not? So, to prove a given Language L is not regular we use a method called **Pumping Lemma.**

The term **Pumping Lemma **is made up of two words:

**Pumping:**The word pumping refers to generate many input strings by pushing a symbol in an input string again and again.**Lemma:**The word Lemma refers to intermediate theorem in a proof.

**Pumping Lemma **is used to prove that given language is not regular. So, first of all we need to know when a language is called regular. A language is called regular if:

- Language is accepted by finite automata.
- A regular grammar can be constructed to exactly generate the strings in a language.
- A regular expression can be constructed to exactly generate the strings in a language.

### Principle of Pumping Lemma

The pumping lemma states that all the regular languages have some special properties. If we can prove that the given language does not have those properties, then we can say that it is not a regular language.

**Theorem 1: Pumping Lemma for Regular Languages**

If L is an infinite regular language then there exists some positive integer n (pumping length) such that any string w ? L has length greater than or equal to n. i.e. **|w| >=n**, then string can be divided into three parts, w=xyz satisfying the following condition:

- For each i>=0, xy
^{i}z ? L. - |y| > 0
- |xy| <= n

**|w|** represents the length of string w and **y ^{i}**means that i copies of y are concatenated together,

**y**

^{0 }=**?.**

### Applying Pumping Lemma

We will use above theorem to prove that given language is not regular. The steps needed to prove that given languages is not regular are given below:

**Step1: **Assume L is a regular language in order to obtain a contradiction. Let n be the number of states of corresponding finite automata.

**Step2: **Now chose a string w in L that has length n or greater

i.e. |w| >= n. use pumping lemma to write

w = xyz with |xy| <= n and |y| = 0.

**Step3: **Finally demonstrate that we cannot pumped by considering all ways of dividing w into x, y and z, and for each such division find a value of I such that xy^{i}z ? L. This contradicts our assumption; hence L is not regular.

We prove xy^{i}z ? L by considering the length of xyz i.e. |xy^{i}z| or by using the structure of strings in L.

**Example**

Let L= { a^{n}b^{n} | n>=0 }. By using pumping lemma show that L is not regular language.

**Solution:**

**Step1: **Assume L is a regular language in order to obtain contradiction. Let n be the number of states in finite automata accepting L.

**Step2:** Let w = a^{n}b^{n}, then |w| = 2n > n. Using pumping lemma, we can demonstrate w in three parts of xyz such that w = xyz with |xy| <=n and |y| > 0.

**Step3: **Now we want to find i, xy^{i}z ? L.

There are three possibilities for y, we will consider all cases one by one and show that given language contains some string not for { a^{n}b^{n} | n>=0 }.

**Case 1: **The string y consists of only a’s i.e. y = a^{k } (k>=1).

We have w = xyz

w = a^{n}b^{n}

In given language we have equal numbers of a’s and b’s w ? L so it must satisfy this condition. Let us take i=0.

As xyz = a^{n}b^{n}

xz = a^{n-k}b^{n}

n-k ? n

So xz ? L. This case is a contradiction.

**Case 2: **The string y consists of only b’s i.e. y = b^{m } (m >= 1).

We have w = xyz

w = a^{n}b^{n}

In given language, we have equal number of a’s and b’s w ? L, so it must satisfy this condition. Let us take i=0.

As xz = a^{n}b^{n-m}

xz = a^{n-k}b^{n}

Where n ? m

So xz ? L. This case also gives contradiction.

**Case 3: **The string y consists of both a’s and b’s i.e. y = a^{k}b^{m } (k,m >= 1).

We have w = xyz

w = a^{n}b^{n}

w = a^{n-k}a^{k}b^{m }b^{n-m}

In given language we have equal number of a’s and b’s w ? L, so it must satisfy this condition. Let us take i=2.

xy^{2}z = xyyz^{i}

= a^{n-k}a^{k}b^{mk}b^{m }b^{n-m}

In this case, the string xyyz must have equal number of a’s and b’s but they are out of order with some b’s before a’s. Hence it is not a member of L. which contradicts our assumption.

Thus, in all cases we get a contradiction. Therefore, **L is not regular.**