Pumping Lemma
Lemma
“Lemma” is defined as a statement that is thought
to be true and is used as the basis of testing the
truth of another statement.
Pumping Lemma for Regular Language
“Pumping Lemma for Regular Languages” is a lemma that
describes an essential property of all regular languages.
Long Strings in a Regular Language may be pumped i.e.
they have a middle section of the string repeated an
arbitrary number of times to produce a new string
belonging the given Regular Language.
Pumping Lemma for Regular Language
Pumping Lemma says that for any regular language L
there exists a constant ‘p’ such that any string w
belonging to L with minimum length ‘p’ can be split into
three substrings x, y and z i.e. “w=xyz” with y being non-
empty, such that the strings xz, xyz, xyyz, xyyyz,... are
constructed by repeating y zero or more times are also
belonging to L.
This process of repetition is known as "pumping".
Pumping Lemma for Regular Language
Pumping Lemma ensures that the length of xy will be at
most p, imposing a limit on the ways in which w may be
split.
Finite Languages satisfy the pumping lemma by having p
equal to the maximum string length in L plus one.
The pumping lemma is useful for disproving the regularity
of a specific language in question.
Proposed by Michael Rabin and Dana Scott in 1959.
Pumping Lemma for Regular Language
Every Language is not Regular.
To show that a language is not regular, we can
use the mechanism termed as “Pumping
Lemma”.
Theorem:
Let L be a Regular Language. The , ∃ a constant
‘n’ such that every string ‘w’ ∈ L and |w| > n, ‘w’
can be broken into three parts x,y and z such that
“w=xyz” and y ≠ ϵ and |xy|< n. Then ∀ i > 0, the
string xyiz ∈ L.
Proof:
Let M be the DFA corresponding to the language
L ‘n’ be the number of states in it.
The ‘n’ is the desired constant.
Let ‘w’ be the string ∈ language L.
|w| = m > n.
Let w=a1a2a3…am-1am.
Proof: …
Let q0 be the starting state for the Finite State
Automation M and δ be the Transition Function.
Then δ(q0, a1a2a3…am-1am) leads to the final state by
passing through the intermediate state(s) in M.
Let S=(q0,q1,q2, …,qm) be the sequence of these states.
As m > n, all these states cannot be distinct.
Repetition is bound to occur.
Proof: …
Let the first repetition occur at qj=qk. Then the
sequence S can be divided into following three
parts “x={q0,q1,q2,…, qj)”, “y={qj+1,qj+2,qj+3,…, qk)”
and “z={qk+1,qk+2,qk+3,…, qm)” and the path of
acceptance is given by
x y z
qk
q0 qj qm
=qj
Proof: …
As k < n and |xy|< n, every repetition of ‘y’ keeps
the acceptance path unchanged, thereby not
affecting the string acceptance mechanism.
Hence, if “xy1z” is accepted by the FSA M, then
“xy2z”, “xy3z”, and so on are also accepted by the FSA
M.
Hence for every positive integral value ‘i’, the string
“xyiz” is accepted by the FSA M.
Application of Pumping Lemma
Pumping Lemma can be used to prove that the
given language L is not regular.
Example1 : Application of Pumping
Lemma
Using Pumping Lemma, prove that the language
L={0s|s is a perfect square} is not Regular
Language.
Proof:
The language under consideration is L={00, 01,04,
09, …} = {ϵ, 0, 0000, 000000000, … }.
Example1 : Application of Pumping
Lemma
Let L={00, 01,04, 09, …} = {ϵ, 0, 0000, 000000000, …
} be a Regular Language and M be the
corresponding FSA with number of states = n.
Let “w” ∈ L and |w|=n2.
Since, ‘n’ is a positive integer, n2 > n. hence “w’
can be broken as “w=xyz” with |xy|< n and |y| >
0.
Example1 : Application of Pumping
Lemma
Since “w = xyz” ∈ L then by Pumping Lemma xy2z
should also ∈ L.
Since, ‘n’ is a positive integer, n2 > n. hence “w’
can be broken as “w=xyz” with |xy|< n and |y| >
0.
|xy2z| = |x| +2|y| + |z| > |x| + |y| + |z|
Example1 : Application of Pumping
Lemma
Hence |xy2z| = > n2 (∵ |y|> 0 ⇒ |y| > 1)
Also, |xy2z| < |xyz| + |xz|
⇒ |xy2z| < n2 + n
⇒ |xy2z| < n2 + 2n + 1
⇒ |xy2z| < (n+1)2
∴ n2 < |xy2z| < (n+1)2
Example1 : Application of Pumping
Lemma
Hence the value of |xy2z| lies between two
consecutive squares.
Hence |xy2z|is not a perfect square.
Hence |xy2z|∉ L.
Since, for given “w= xyz” ∈ L, |xy2z|∉ L.
Hence, the language L is not Regular Language.
Example2 : Application of Pumping
Lemma
Using Pumping Lemma, prove that the language
L={0P|P is a prime number} is not Regular
Language.
Proof:
The language under consideration is L={02, 03,05,
07, …} = {00, 000, 00000, 0000000 … }.
Example2 : Application of Pumping
Lemma
Let L={02, 03,05, 07, …} = {00, 000, 00000, 0000000
… } be a Regular Language and M be the
corresponding FSA with number of states = n.
Let “w” ∈ L and |w|=P, where P is prime number
such that p > n.
Hence “w’ can be broken as “w=xyz” with |xy|< n
and |y| > 0.
Example2 : Application of Pumping
Lemma
Since “w = xyz” ∈ L then for L to be Regular
Language xyiz should also ∈ L for every value of ‘i’.
|xyiz| = |xyz| + |y(i – 1)| (∵ |y| > 0 )
Let |y| = k then k > 0.
If, we take i = P +1, then |xyiz| = P + k(P + 1 – 1)
∴ |xyiz| = P + Pk = P(1+k)
Example2 : Application of Pumping
Lemma
But |xyiz| is composite for I = (P + 1).
Hence xyiz ∉ L
∴ L is not a Regular Language.
Example3 : Application of Pumping
Lemma
Using Pumping Lemma, prove that the language
L={w|w is a palindrome over (0,1)} is not Regular
Language.
Proof:
Let the language under consideration i.e. L is a
regular language and M is the corresponding FSA
with number of states = n.
Example3 : Application of Pumping
Lemma
Let the palindrome string “w= 1n01n” over the (0,
1).
By observing the above, we can find that |w| > n.
∴ “w” can be broken as “w = xyz” such that |xy| <
n and |y| > 0.
∵ |xy| < n ⇒ “xy” is a string of 1’s.
Example3 : Application of Pumping
Lemma
∴ Let |xy| = n and |x| = k, then |y| = n - k.
∵ “w=xyz” can be written as 1k1n – k01n.
∵ “w=xyz” ∈ L
∴ for L to be regular xyiz ∈ L for every value of i.
But, xyiz = 1k1n - k01n, which is not a palindrome
string.
Example3 : Application of Pumping
Lemma
∴ xyiz ∉ L ∀ i.
∴ L is not a Regular Language.
Pumping Lemma for Context Free
Language: Theorem
Let L be a CFL. Then, ∃ a positive integer ‘m’ such
that for any string z ∈ L, if |z| > m, ‘z’ can be
broken into uvwxy such that |vwx| < m and |vx| >
1 and for every positive integer ‘k’, we have
uvkwxky ∈ L.
Pumping Lemma for Context Free
Language: Theorem
Proof:
Let G (V, ∑, P, S) be the CFG corresponding to CFL L in
CNF.
Let ϵ ∉ L and even if so, then we can create a version
of L such that L = L – {ϵ}. This will remove any
possibility of null production in G. Here we are taking
care about the string(s) with the length > m, where
‘m’ is a positive integer i.e. m > 1.
Pumping Lemma for Context Free
Language: Theorem
Let |V| = n, then m = 2nis the required positive
integer.
∵ z ∈ L
∴ a derivation tree (say T) can be constructed for
the string “z” with its head as S.
∵ |z| > m = 2n and the grammar is in the CNF,
there must be a path of length > n in the tree T.
Pumping Lemma for Context Free
Language: Theorem
When |z| > n then there is a path say P of length >
n in the derivation tree T containing more than n
number of vertices.
∵ |V| = n, all these vertices cannot be distinct.
There has to be repetition of the vertices in the
path P.
Pumping Lemma for Context Free
Language: Theorem
Let B be such vertex. Let there be two B’s in the
path P. One is closer to root and other is closer to
leaf.
For the B closer to the root (say S), the yield for S
can be “uBy” , where “u” is the string created on
LHS of B and “y” is the string created on RHS of B.
Pumping Lemma for Context Free
Language: Theorem
Now, in the path to the leaf from the above B,
there exists another B.
Hence the yield of B (closer to root) at the B
(closer to the leaf) can be written as “vBx”, where
“v” is the string created on the LHS of B and “x” is
the string generated on RHS of B.
Pumping Lemma for Context Free
Language: Theorem
Hence the yield of S at the second B(closer to leaf)
can be written as “uvBxy”.
Let “w” be the string of the terminals derived by
B at the leaf level, then the yield for S can be
rewritten as “uvwxy”.
In case of three B’s in the path from root S to the
leaf, then the yield will be uvvwxxy.
Pumping Lemma for Context Free
Language: Theorem
Similarly, in case of “k + 1” B’s in the path from
root S to the leaf, then the yield will be uvkwxky.
Thus, in the parse tree for the string “z” of length
> m, there exists multiple occurrences of the some
variable (say B) and
S → *uBy
B → *uBx | w
Pumping Lemma for Context Free
Language: Theorem
We have , S → *uBy → *uvBxy → *uvwxy = z.
Hence for every z ∈ L, the terminal derivation is
coming from B → *w.
As the grammar is unambiguous, the only path to
“vBx” is through “B” i.e. “uvBxy”, where B could
have been replaced by “vBx”.
Pumping Lemma for Context Free
Language: Theorem
Hence, if “uvwxy” ∈ L ⇒ “uvvwxxy” ∈ L and so on.
Since, there are no null productions in vBx, we
have |vx| > 1.
In case of “vBx”, the variable “B” is replaced by
“w” in its first occurrence. Hence there is no
repetition of variable B and hence |vwx| < m.
Example1 : Application of Pumping
Lemma for CFL
Using Pumping Lemma, prove that the language
L={0S|S is a prefect square} is not CFL.
Proof:
The language under consideration is L={00, 01,04,
09, …} = {ϵ, 0, 0000, 000000000 … }.
Example1 : Application of Pumping
Lemma for CFL
Step 1: Let m be the required positive integer.
Step 2: Let n = m2 be a perfect square and z = 0n ∈
L. Let z = uvwxy, where |vwx| < m and |vx| > 1
and both “v” and “x” are not null.
Step 3: Since, z = uvwxy ∈ L, by pumping lemma,
uv2wx2y ∈ L. Since |wx| > 1, |uv2wx2y| > |uvwxy|
i.e. |uv2wx2y| > m2.
Example1 : Application of Pumping
Lemma for CFL
Step 4: |uv2wx2y| + |uvwxy| + |vx| < |uvwxy| +
|vwx| < m2 + m < (m+1)2.
Step 5: (m + 1)2 > |uv2wx2y| > m2. since |uv2wx2y|
lies between two consecutive perfect square
numbers, it cannot be perfect square and hence
for a given string “z = uvwxy” ∈ L, uv2wx2y ∉ L and
subsequently uviwxiy ∉ L and hence L={0S|S is a
prefect square} is not CFL.
