More Applications

of

the Pumping Lemma

1
 The Pumping Lemma:
• Given a infinite regular language L
• there exists an integer m (critical length)
• for any string w L with length | w |  m
• we can write w x y z

• with | x y |  m and | y |  1
i i  0, 1, 2, ...
• such that: xy z  L
2
Non-regular languages R
L  {vv : v  *}

Regular languages

3
Theorem: The language
R
L  {vv : v  *}   {a, b}
is not regular

Proof: Use the Pumping Lemma

4
 R
L  {vv : v  *}

Assume for contradiction

that L is a regular language

Since L is infinite
we can apply the Pumping Lemma

5
 R
L  {vv : v  *}
Let m be the critical length for L

Pick a string w such that: w  L

and length | w| m

m m m m
We pick wa b b a
6
From the Pumping Lemma:

we can write: w  a b b a x y z
m m m m

with lengths: | x y |  m, | y | 1

m m m m
w  xyz  a...aa...a...ab...bb...ba...a
x y z

Thus: y a , 1k m
k

7
 m m m m
x y za b b a y a , 1k m
k

i
From the Pumping Lemma: xy z  L
i  0, 1, 2, ...

2
Thus: xy z  L
8
 m m m m
x y za b b a y a , 1k m
k

2
From the Pumping Lemma: xy z  L

m + k m m m
2
xy z = a...aa...aa...a...ab...bb...ba...a ∈L
x y y z

m k m m m
Thus: a b b a L
9
 m k m m m
a b b a L k 1

BUT: R
L  {vv : v  *}

m k m m m
a b b a L

CONTRADICTION!!!
10
Therefore: Our assumption that L
is a regular language is not true

Conclusion: L is not a regular language

END OF PROOF
11
Non-regular languages
n l n l
L  {a b c : n, l  0}

Regular languages

12
Theorem: The language
n l n l
L  {a b c : n, l  0}
is not regular

Proof: Use the Pumping Lemma

13
 n l n l
L  {a b c : n, l  0}

Assume for contradiction

that L is a regular language

Since L is infinite
we can apply the Pumping Lemma

14
 n l n l
L  {a b c : n, l  0}
Let m be the critical length of L

Pick a string w such that: w  L and

length | w| m

We pick m m 2m
wa b c
15
From the Pumping Lemma:

We can write w a b c m m 2m
x y z
With lengths | x y |  m, | y | 1

m m 2m
w  xyz  a...aa...aa...ab...bc...cc...c
x y z

Thus: y a , 1k m
k

16
 m m 2m
x y za b c y a , 1k m
k

i
From the Pumping Lemma: xy z  L
i  0, 1, 2, ...

0
Thus: x y z = xz ∈ L

17
 m m 2m
x y za b c y a , 1k m
k

From the Pumping Lemma: xz  L

mk m 2m
xz  a...aa...ab...bc...cc...c  L
x z

mk m 2m
Thus: a b c L
18
 mk m 2m
a b c L k 1

BUT: n l n l
L  {a b c : n, l  0}

mk m 2m
a b c L

CONTRADICTION!!!
19
Therefore: Our assumption that L
is a regular language is not true

Conclusion: L is not a regular language

END OF PROOF
20
 n!
Non-regular languages L  {a : n  0}

Regular languages

21
Theorem: The language n!
L  {a : n  0}
is not regular

n!  1  2  (n  1)  n

Proof: Use the Pumping Lemma

22
 n!
L  {a : n  0}

Assume for contradiction

that L is a regular language

Since L is infinite
we can apply the Pumping Lemma

23
 n!
L  {a : n  0}
Let m be the critical length of L

Pick a string w such that: w  L

length | w| m

m!
We pick wa
24
From the Pumping Lemma:

We can write w  a x y z
m!

With lengths | x y |  m, | y | 1
m m! m
m!
w  xyz  a  a...aa...aa...aa...aa...a
x y z
k
Thus: y  a , 1 k  m
25
 m! k
x y za y  a , 1 k  m

i
From the Pumping Lemma: xy z  L
i  0, 1, 2, ...

Thus: 2
xy z  L

26
 m! k
x y za y  a , 1 k  m

2
From the Pumping Lemma: xy z  L

mk m! m
2
xy z  a...aa...aa...aa...aa...aa...a  L
x y y z

Thus: m! k
a L
27
 m! k
a L 1 k  m

Since: n!
L  {a : n  0}

There must exist p such that:

m! k  p!

28
However: m! k  m! m for m 1
 m! m!
 m!m  m!
 m!(m  1)
 (m  1)!

m! k  (m  1)!

m! k  p! for any p

29
 m! k 1 k  m
a L

n!
BUT: L  {a : n  0}

m! k
a L

CONTRADICTION!!!
30
Therefore: Our assumption that L
is a regular language is not true

Conclusion: L is not a regular language

END OF PROOF
31
 More examples
• Prove using pumping lemma that the
following languages are not regular

1. L = {1p | p is prime number}

2
2. L = {a | i>=1}
i

3. L = {ww | w Є (0,1)*}

32