Pumping lemma for cfl

PUMPING LEMMA
There are two Pumping Lemmas, which are defined for
1. Regular Languages, and
2. Context – Free Languages

APPLICATIONS OF PUMPING LEMMA
Pumping Lemma is to be applied to show that certain
languages are not regular.
It should never be used to show a language is regular.
 If L is regular, it satisfies Pumping Lemma.
 If L does not satisfy Pumping Lemma, it is non-
regular.

FORMAL STATEMENT
Pumping Lemma for Regular Languages
For any regular language L, there exists an integer n, such that for all w ∈
L with
|w| ≥ n, there exists (x, y, z ∈ Σ∗), such that w = xyz, and
(1) |xy| ≤ n
(2) |y| ≥ 1
(3) for all i ≥ 0: xyiz ∈ L
In simple terms, this means that if a string y is ‘pumped’, i.e., if y is
inserted any number of times, the resultant string still remains in L.

FORMAL STATEMENT
Pumping Lemma for Context-free Languages (CFL)
Pumping Lemma for CFL states that for any Context Free Language L, it is
possible to find two substrings that can be ‘pumped’ any number of times
and still be in the same language. For any language L, we break its strings
into five parts and pump second and fourth substring.
Pumping Lemma, here also, is used as a tool to prove that a language is not
CFL. Because, if any one string does not satisfy its conditions, then the
language is not CFL.

| w| n
The Pumping Lemma:
For infinite context-free language L
there exists an integer n such that
for any string
we can write
with lengths and |vy |1
w L,
w =uvxyz
| vxy | n
for all i  0
and it must be:
uvi xyiz  L,

TAKE AN INFINITE CONTEXT-FREE
LANGUAGE
Example: S → AB
A →aBb
B → Sb
B → b
Generates an infinite number
of different strings

S → AB
A →
ABB B
→ SB B
→B
A derivation:
S  AB  aBbB abbB
 abbSb  abbABb  abbaBbBb 
 abbabbBb  abbabbbb
In a derivation of a long string,
variables are repeated

S
A B
bBa
b
bS
A B
bBa
b
b
Derivation tree string abbabbbb

S
A B
bBa
b
bS
A B
bBa
b
b
repeated
Derivation tree string abbabbbb

B
bS
A B
bBa b
B  Sb  ABb 
 aBbBb  aBbbb
B b
b
*
BaBbbb

B
bS
A B
bBa b
Repeated Part
*
BaBbbb

B
bS
A B
ba bB
bS
A B
bBa b
* *
BaBbbbaaBbbbbbb
Another possible
*
BaBbbb
derivation from B

B
bS
A B
ba bB
bS
A B
bBa b
22
* *
B (a)B(bbb)(a) B(bbb)
*
BaBbbb

22
*
S  abb(a) b(bbb)
abb(a)2b(bbb)2 L(G)
*
B aBbbb B b
*
SabbBb

S
A B
bBa
b
*
BaBbbb
B  b
*
SabbBb
S abbBb  abbbb
*
b
= abb(a)0b(bbb)0

00
*
S  abb(a) b(bbb)
*
B aBbbb B b
*
SabbBb

33 3 3
*
S  abb(a) B(bbb)  abb(a) b(bbb)
S
A B
B ba
b
bS
A B
ba bB
bS
A B
B ba b
bS
A B
bBa b
b
*
BaBbbb
B  b
*
S  abbBb

33
*
S  abb(a) b(bbb)
*
B aBbbb B b
*
SabbBb

ii
*
S abb(a) b(bbb)
abb(a)ib(bbb)i L(G)
*
B aBbbb B b
*
SabbBb
In General:
i 0

S
A
x
u
Last repeated variable
z
v y
w =uvxyz
u,v, x, y, z :
repeated A
Strings of terminals
DERIVATION TREE OF
STRING W

S
A
A
x
u z
v y

SuAz

AvAy

Ax
Possible
derivations:

 
S uAz AvAy

Ax
We know:
This string is also generated:
 *
S uAzuxz
uv0xy0z

 * *
S uAzuvAyzuvxyz
The original w =uv1xy1z
 
S uAz AvAy

Ax
We know:

 * * *
S uAzuvAyzuvvAyyzuvvxyyz
uv2xy2z
 
S uAz AvAy

Ax
We know:

 * *
S uAz  uvAyzuvvAyyz
* *
uvvvAyyyzuvvvxyyyz
uv3xy3z
 
S uAz AvAy

Ax
We know:

We know:
  
S uAz AvAy A x
S  uAz  uvAyz  uvvAyyz 
 uvvvAyyyz …
 u v v v v A y yyyz 
 u v v v v x y yyyz
uvi xyiz

Therefore, any string of the form
uvixyiz
is generated by the grammar G
i 0

knowing that uvxyz  L(G)
we also know that uvixyiz L(G)
Therefore,
L(G) = L−{}
uvi xyiz L

S
A
A
u z
v y
x
| vxy |  mObservation:
Since A is the last repeated variable

S
A
u z
v y
A
x
Observation: | vy |  1
Since there are no unit or -productions

Pumping lemma for cfl

Recommended

Recommended

More Related Content

What's hot

What's hot (20)

Similar to Pumping lemma for cfl

Similar to Pumping lemma for cfl (20)

Recently uploaded

Recently uploaded (20)

Pumping lemma for cfl