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 xyiz 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 :

  1. Select a string z in the language L.
  2. Break the string z into x, y and z in accordance with the above conditions imposed by the pumping lemma.
  3. 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

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

  1. Prove that Language L = {anbn for n>=0} is not regular.
  2. 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 = aj z = bn 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.

Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.