More Applications
of
The Pumping Lemma
The Pumping Lemma:
For infinite context-free language
there exists an integer
w L,
for any string
such that
| w | m
we can write
w uvxyz
with lengths
| vxy | m and | vy | 1
and it must be:
i i
uv xy z L,
for all i 0
Non-context free languages
n n n
{a b c : n 0}
{vv : v {a, b}}
Context-free languages
n n
{a b : n 0}
{ww : w {a, b}*}
Theorem: The language
L {vv : v {a, b}*}
is not context free
Proof:
Use the Pumping Lemma
for context-free languages
L {vv : v {a, b}*}
Assume for contradiction that
is context-free
Since L is context-free and infinite
we can apply the pumping lemma
L {vv : v {a, b}*}
Pumping Lemma gives a magic number
such that:
Pick any string of
we pick:
with length at least
m m m m
a b a b
L {vv : v {a, b}*}
We can write:
with lengths
m m m m
a b a b uvxyz
| vxy | m
and
| vy | 1
Pumping Lemma says:
i
uv xy z L
for all
i0
L {vv : v {a, b}*}
m m m m
a b a b uvxyz
| vxy | m
| vy | 1
We examine all the possible locations
m m m m
of string vxy in a b a b
L {vv : v {a, b}*}
m m m m
| vxy | m
a b a b uvxyz
Case 1:
va
vxy
k1
is within the first
ya
k2
| vy | 1
a
k1 k 2 1
m
m
m
m
a ...... a b ...... b a ...... a b ...... b
z
u vx y
L {vv : v {a, b}*}
m m m m
| vxy | m
a b a b uvxyz
Case 1:
va
vxy
k1
is within the first
ya
k2
| vy | 1
a
k1 k 2 1
m
m
m k1 k 2 m
a ................ a b ...... b a ...... a b ...... b
z
u v2 x y2
L {vv : v {a, b}*}
m m m m
a b a b uvxyz
Case 1:
vxy
| vxy | m
is within the first
m k1 k 2 m m m
| vy | 1
a
b a b uv xy z L
k1 k 2 1
L {vv : v {a, b}*}
m m m m
a b a b uvxyz
Case 1:
vxy
| vxy | m
is within the first
m k1 k 2 m m m
| vy | 1
a
b a b uv xy z L
However, from Pumping Lemma:
Contradiction!!!
uv xy z L
L {vv : v {a, b}*}
m m m m
| vxy | m
a b a b uvxyz
Case 2: v
va
| vy | 1
m
is in the first a
m
is in the first b
k1
yb
k2
k1 k 2 1
m
m
m
m
a ...... a b ...... b a ...... a b ...... b
z
u v x y
L {vv : v {a, b}*}
m m m m
| vxy | m
a b a b uvxyz
Case 2: v
va
| vy | 1
m
is in the first a
m
is in the first b
k1
yb
k2
k1 k 2 1
m
m
m k1
m k2
a ............ a b ............ b a ...... a b ...... b
2 x
2
z
u
v
y
L {vv : v {a, b}*}
m m m m
| vxy | m
a b a b uvxyz
Case 2: v
| vy | 1
m
is in the first a
m
is in the first b
m k1 m k 2 m m
k1 k 2 1
a b uv xy z L
L {vv : v {a, b}*}
m m m m
| vxy | m
a b a b uvxyz
Case 2: v
m
is in the first a
m
is in the first b
m k1 m k 2 m m
| vy | 1
a b uv xy z L
However, from Pumping Lemma:
Contradiction!!!
uv xy z L
L {vv : v {a, b}*}
m m m m
| vxy | m
a b a b uvxyz
| vy | 1
m m
Case 3: v overlaps the first a b
k1 k 2
a b
is in the first
y b
k3
k1, k 2 1
m
m
m
m
a ...... a b ...... b a ...... a b ...... b
u
v xy z
L {vv : v {a, b}*}
m m m m
| vxy | m
a b a b uvxyz
| vy | 1
m m
Case 3: v overlaps the first a b
k1 k 2
a b
is in the first
y b
k3
k1, k 2 1
k2
k1 m k3
m
m
m
a ...... a b ... b a ... a b ......... b a ...... a b ...... b
u
2
2
z
x
v
y
L {vv : v {a, b}*}
m m m m
| vxy | m
a b a b uvxyz
| vy | 1
m m
Case 3: v overlaps the first a b
is in the first
m k 2 k1 m k3 m m
a b a b
a b
k1, k 2 1
m
2
uv xy z L
L {vv : v {a, b}*}
m m m m
| vxy | m
a b a b uvxyz
| vy | 1
m m
Case 3: v overlaps the first a b
is in the first
m k 2 k1 k3 m m
a b a b a b
uv xy z L
However, from Pumping Lemma:
Contradiction!!!
uv xy z L
L {vv : v {a, b}*}
m m m m
| vxy | m
a b a b uvxyz
Case 4: v in the first a
Overlaps the first
m m
a b
Analysis is similar to case 3
m
m
m
m
a ...... a b ...... b a ...... a b ...... b
z
uv x y
| vy | 1
Other cases:
vxy
is within
m m m m
a b a b
or
m m m m
a b a b
or
m m m m
a b a b
Analysis is similar to case 1:
m m m m
a b a b
More cases:
vxy
overlaps
m m m m
a b a b
or
m m m m
a b a b
Analysis is similar to cases 2,3,4:
m m m m
a b a b
There are no other cases to consider
Since | vxy | m, it is impossible
vxy to overlap:
m m m m
a b a b
nor
m m m m
a b a b
nor
m m m m
a b a b
In all cases we obtained a contradiction
Therefore: The original assumption that
L {vv : v {a, b}*}
is context-free must be wrong
Conclusion:
is not context-free
Non-context free languages
{ww : w {a, b}}
n n n
{a b c : n 0}
n!
{a : n 0}
Context-free languages
n n
{a b : n 0}
{ww : w {a, b}*}
Theorem: The language
n!
L {a : n 0}
is not context free
Proof:
Use the Pumping Lemma
for context-free languages
n!
L {a : n 0}
Assume for contradiction that
is context-free
Since L is context-free and infinite
we can apply the pumping lemma
n!
L {a : n 0}
Pumping Lemma gives a magic number
such that:
Pick any string of
we pick:
L
a
m!
with length at least
n!
L {a : n 0}
We can write:
with lengths
m!
uvxyz
| vxy | m
and
| vy | 1
Pumping Lemma says:
i
uv xy z L
for all
i0
n!
L {a : n 0}
a
m!
uvxyz
| vxy | m
| vy | 1
We examine all the possible locations
m!
of string vxy in a
There is only one case to consider
n!
L {a : n 0}
a
m!
| vxy | m
uvxyz
| vy | 1
m!
a ............... a
u v x y z
va
k1
ya
k2
1 k1 k 2 m
n!
L {a : n 0}
a
m!
| vxy | m
uvxyz
| vy | 1
m! k1 k 2
a ........................... a
u v2 x y2 z
va
k1
ya
k2
1 k1 k 2 m
n!
L {a : n 0}
a
m!
| vxy | m
uvxyz
m! k
a ........................... a
u v2 x y2 z
va
k1
ya
k2
| vy | 1
k k1 k 2
1 k m
n!
L {a : n 0}
a
m!
| vxy | m
uvxyz
m! k
uv xy z
1 k m
| vy | 1
Since
1 k m,
for
m2
we have:
m! k m! m
m! m!m
m!(1 m)
(m 1)!
m! m! k (m 1)!
n!
L {a : n 0}
a
m!
uvxyz
| vxy | m
m! m! k (m 1)!
m! k
uv xy z L
| vy | 1
n!
L {a : n 0}
a
m!
uvxyz
| vxy | m
However, from Pumping Lemma:
m! k
| vy | 1
2
uv xy z L
uv xy z L
Contradiction!!!
We obtained a contradiction
Therefore: The original assumption that
n!
L {a : n 0}
is context-free must be wrong
Conclusion:
is not context-free
Non-context free languages
n n n
{a b c : n 0}
n
{a b : n 0}
{ww : w {a, b}}
n!
{a : n 0}
Context-free languages
n n
{a b : n 0}
{ww : w {a, b}*}
Theorem: The language
2
n n
L {a b : n 0}
is not context free
Proof:
Use the Pumping Lemma
for context-free languages
L {a b : n 0}
Assume for contradiction that
is context-free
Since L is context-free and infinite
we can apply the pumping lemma
L {a b : n 0}
Pumping Lemma gives a magic number
such that:
Pick any string of
we pick:
with length at least
L {a b : n 0}
We can write:
with lengths
b uvxyz
| vxy | m
and
| vy | 1
Pumping Lemma says:
i
uv xy z L
for all
i0
L {a b : n 0}
a
| vxy | m
b uvxyz
| vy | 1
We examine all the possible locations
of string
vxy
in
L {a b : n 0}
a
b uvxyz
Most complicated case:
| vxy | m
v
y
m
is in a
m
is in b
m
m
a ..................... a b ...... b
u
v x y z
| vy | 1
L {a b : n 0}
a
va
| vxy | m
b uvxyz
k1
y b
k2
| vy | 1
1 k1 k 2 m
m
m
a ..................... a b ...... b
u
v x y z
L {a b : n 0}
a
b uvxyz
| vxy | m
| vy | 1
k1 0
k2 0
Most complicated sub-case:
va
k1
y b
k2
and
1 k1 k 2 m
m
m
a ..................... a b ...... b
u
v x y z
L {a b : n 0}
a
b uvxyz
| vxy | m
| vy | 1
k1 0
k2 0
Most complicated sub-case:
va
k1
y b
k2
and
1 k1 k 2 m
m k1 m k 2
a ............... a b ... b
u
0 x 0z
v
L {a b : n 0}
a
b uvxyz
| vxy | m
| vy | 1
k1 0
k2 0
Most complicated sub-case:
va
k1
y b
a
k2
m 2 k1 m k 2
and
1 k1 k 2 m
0
uv xy z
k1 0
and
k2 0
1 k1 k 2 m
2
(m k 2 ) (m 1)
m 2m 1
2
m k1
2
m k1 (m k 2 )
L {a b : n 0}
a
b uvxyz
| vxy | m
m k1 (m k 2 )
2
m k1 m k2
a
b
uv xy z L
| vy | 1
L {a b : n 0}
a
b uvxyz
| vxy | m
0
m k1 m k2
a
b
uv xy z L
However, from Pumping Lemma:
| vy | 1
uv xy z L
Contradiction!!!
When we examine the rest of the cases
we also obtain a contradiction
In all cases we obtained a contradiction
Therefore: The original assumption that
n
L {a b : n 0}
is context-free must be wrong
Conclusion:
is not context-free