**Lemma** :* The pumping lemma states that for a regular language L, there exists a constant n such that every string w in L ( such that length of w (|w|) >= n) we can break w into three substrings, w = xyz, such that *

- y is not null
- |xy| <= n
- For all i >= 0, the string xy
^{i}z is also in L

Note that |x| and |z| can be 0 but |y| has to be greater than 1.

The lemma states that for a regular language every string can be broken into three parts x,y and z such that if we repeat y i times between x and z then the resulting string is also present in L.

**Applications of the Pumping Lemma**

The pumping lemma is extremely useful in proving that certain sets are non-regular. The general methodology followed during its applications is :

- Select a string z in the language L.
- Break the string z into x, y and z in accordance with the above conditions imposed by the pumping lemma.
- Now check if there is any contradiction to the pumping lemma for any value of i.

It is suggested that you try out the questions before looking at the solutions.

**Example question: Prove that the language of palindromes over {0, 1} is not regular. **

View Answer

**Solution:**

Let L be a regular language and n be the integer in the statement of the pumping lemma. To prove that the language is not regular we must choose a string w of length n that will produce contradiction. Let us consider the string O

^{n}1 O

^{n}. Let y be of the form O

^{j}where j > 0. So according to the pumping lemma O

^{(n-j)}(O

^{j})

^{i}1 O

^{n}should be in L for all values of i >= 0. But for i = 0 the string becomes O

^{(n-j)}1 O

^{n}, which is not a palindrome for any positive value of j. This contradicts the pumping lemma for L hence L is not a regular language.

- Prove that Language L = {a
^{n}b^{n}for n>=0} is not regular. - Prove that the language containing strings of balanced parentheses is not regular.

View Answer

- Following the same procedure as described in the above example you can prove that the string of the form x = a
^{(n-j)}y = a^{j}z = b^{n}contradicts pumping lemma for i = 0. - The language will contain strings of the form (()()()), (((()))), ((()()())), …. Let the language be a regular language. Suppose we choose a string of the form (
^{n})^{n}. Now choosing x, y and z as in the above question we arrive at a contradiction to the pumping lemma. Hence the language is not regular.

**Sanfoundry Global Education & Learning Series – 100+ Theory of Computation Tutorials.**

If you wish to look at all Tutorials and their examples, go to Theory of Computation Tutorials.