Theory of Computation - Pumping Lemma for Regular Languages and its Application

Every regular Language can be accepted by a finite automaton, a recognizing device with a finite set of states and no auxiliary memory. This finiteness of the set is used by the pumping lemma in proving that a language is not regular. It is important to note that pumping lemma is not used for proving whether a language is regular. It is rather used for proving if the language is not regular.

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ⁱ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ⁿ 1 Oⁿ. Let y be of the form O^j where j > 0. So according to the pumping lemma O^(n-j) (O^j)ⁱ1 Oⁿ should be in L for all values of i >= 0. But for i = 0 the string becomes O^(n-j)1 Oⁿ, 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.

Questions:

Prove that Language L = {aⁿbⁿ 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ⁿ 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 (ⁿ)ⁿ. 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.

If you find any mistake above, kindly email to [email protected]

« Prev - Theory of Computation – Minimizing a Deterministic Finite Automata

» Next - Theory of Computation – Context Free Grammars (CFG) and Context Free Languages (CFL)

Related Posts:

Recommended Articles: