Short Notes: Pumping Lemma | Theory of Computation - Computer Science Engineering (CSE) PDF Download

 Page 1


Pumping Lemma for regular languages
• Suppose that a language L is regular. Then there is a FA that accepts L.
• Let n be the number of states of that FA. Then for any string x in L with |x| £ n, 
there are strings u, v and w which satisfy the following:
o x = uvw 
° |uv| s n
° |v| > 0 is same as v 1 1 
° For every integer m £ 0, uvm w e L.
• If L is regular then for every x such that |x| £ n then there exists uvw such that 
x=uvw, vtz, |uv| < , n, and for which uv'w is in L for every /'.
Pumping Lemma gives a necessity for regular languages.
Pumping Lemma is not a sufficiency, that is, even if there is an integer n that 
satisfies the conditions of Pumping Lemma, the language is not necessarily 
regular.
Pumping Lemma can not be used to prove the regularity of a language.
It can only show that a language is non-regular.
Example: L = akbkis non-regular, where k is a natural number.
• Suppose that L is regular and let n be the number of states of an FA that 
accepts L. Consider a string x = an bn for that n.
• Then there must be strings u, v, and w such that
• x = uvw, |uv| s n |v| > 0, and for every m £ 0, uvm w e L.
• Since |v| > 0, v has at least one symbol.
• Also since |uv| S n ,v = ap , for some p > 0,
• Let us now consider the string uvm w for m = 2.
Page 2


Pumping Lemma for regular languages
• Suppose that a language L is regular. Then there is a FA that accepts L.
• Let n be the number of states of that FA. Then for any string x in L with |x| £ n, 
there are strings u, v and w which satisfy the following:
o x = uvw 
° |uv| s n
° |v| > 0 is same as v 1 1 
° For every integer m £ 0, uvm w e L.
• If L is regular then for every x such that |x| £ n then there exists uvw such that 
x=uvw, vtz, |uv| < , n, and for which uv'w is in L for every /'.
Pumping Lemma gives a necessity for regular languages.
Pumping Lemma is not a sufficiency, that is, even if there is an integer n that 
satisfies the conditions of Pumping Lemma, the language is not necessarily 
regular.
Pumping Lemma can not be used to prove the regularity of a language.
It can only show that a language is non-regular.
Example: L = akbkis non-regular, where k is a natural number.
• Suppose that L is regular and let n be the number of states of an FA that 
accepts L. Consider a string x = an bn for that n.
• Then there must be strings u, v, and w such that
• x = uvw, |uv| s n |v| > 0, and for every m £ 0, uvm w e L.
• Since |v| > 0, v has at least one symbol.
• Also since |uv| S n ,v = ap , for some p > 0,
• Let us now consider the string uvm w for m = 2.
• Then uv2w = an " pa2pbn = an+pbn. Since p>0,n + p^n.
• Hence an+pbn can not be in the language L represented by akbk.
• This violates the condition that for every m £ 0, uvm w e L.
• Hence L is not a regular language.
Pumping Lemma for CFL’s
• Let L be a CFL. Then there exists a constant N such that if z eL s.t. |z|£N, then 
we can write z=uvwxy,
• |vwx| s N
• vx t e
• For all k £ 0 : uvk wxk y e L