Scribd
Upload
11 views31 pages

Applications of the Pumping Lemma

The document presents the proof that the language L = {an! : n ≥ 0} is not regular. It does so by assuming L is regular and applying the pumping lemma. It picks the string w = am! and shows that pumping w violates the structure of L, obtaining a contradiction. This implies the initial assumption that L is regular must be false, so L is concluded to be a non-regular language.

Uploaded by

Jorge D. Nontol
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
11 views31 pages

Applications of the Pumping Lemma

The document presents the proof that the language L = {an! : n ≥ 0} is not regular. It does so by assuming L is regular and applying the pumping lemma. It picks the string w = am! and shows that pumping w violates the structure of L, obtaining a contradiction. This implies the initial assumption that L is regular must be false, so L is concluded to be a non-regular language.

Uploaded by

Jorge D. Nontol
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd

More Applications

of

the Pumping Lemma

Fall 2006 Costas Busch - RPI 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

such that: xy z L
i i 0, 1, 2, ...
Fall 2006 Costas Busch - RPI 2
Non-regular languages L {vv : v *}
R

Regular languages

Fall 2006 Costas Busch - RPI 3


Theorem: The language

L {vv : v *}
R
{a, b}
is not regular

Proof: Use the Pumping Lemma

Fall 2006 Costas Busch - RPI 4


L {vv : v *}
R

Assume for contradiction


that L is a regular language

Since L is infinite
we can apply the Pumping Lemma

Fall 2006 Costas Busch - RPI 5


L {vv : v *}
R

Let m be the critical length for L

Pick a string w such that: w L


and length | w| m

We pick wa b b a m m m m

Fall 2006 Costas Busch - RPI 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 , 1k m
k

Fall 2006 Costas Busch - RPI 7


x y za b b a
m m m m
y a , 1k m
k

From the Pumping Lemma: xy z L


i

i 0, 1, 2, ...

Thus: xy z L 2

Fall 2006 Costas Busch - RPI 8


x y za b b am m m m
y a , 1k m
k

From the Pumping Lemma: xy z L


2

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
Fall 2006 Costas Busch - RPI 9
m k m m m k 1
a b b a L

BUT: L {vv : v *}
R

m k m m m
a b b a L

CONTRADICTION!!!
Fall 2006 Costas Busch - RPI 10
Therefore: Our assumption that L
is a regular language is not true

Conclusion: L is not a regular language

END OF PROOF
Fall 2006 Costas Busch - RPI 11
Non-regular languages
n l n l
L {a b c : n, l 0}

Regular languages

Fall 2006 Costas Busch - RPI 12


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

Proof: Use the Pumping Lemma

Fall 2006 Costas Busch - RPI 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

Fall 2006 Costas Busch - RPI 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 wa b c m m 2m

Fall 2006 Costas Busch - RPI 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 , 1k m
k

Fall 2006 Costas Busch - RPI 16


x y za b c m m 2m
y a , 1k m
k

From the Pumping Lemma: xy z L


i

i 0, 1, 2, ...

0
Thus: x y z = xz L

Fall 2006 Costas Busch - RPI 17


x y za b c m m 2m
y a , 1k m
k

From the Pumping Lemma: xz L


mk m 2m
xz a...aa...ab...bc...cc...c L
x z

mk m 2 m
Thus: a b c L
Fall 2006 Costas Busch - RPI 18
mk m 2 m k 1
a b c L

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

mk m 2 m
a b c L

CONTRADICTION!!!
Fall 2006 Costas Busch - RPI 19
Therefore: Our assumption that L
is a regular language is not true

Conclusion: L is not a regular language

END OF PROOF
Fall 2006 Costas Busch - RPI 20
Non-regular languages L {a : n 0}
n!

Regular languages

Fall 2006 Costas Busch - RPI 21


Theorem: The language L {a : n 0}
n!

is not regular

n! 1 2 (n 1) n

Proof: Use the Pumping Lemma

Fall 2006 Costas Busch - RPI 22


L {a : n 0}
n!

Assume for contradiction


that L is a regular language

Since L is infinite
we can apply the Pumping Lemma

Fall 2006 Costas Busch - RPI 23


L {a : n 0}
n!

Let m be the critical length of L

Pick a string w such that: w L


length | w| m

We pick wa m!

Fall 2006 Costas Busch - RPI 24


From the Pumping Lemma:

We can write w a x y z
m!

With lengths | x y | m, | y | 1
m m!m
w xyz a a...aa...aa...aa...aa...a
m!

x y z

Thus: y a , 1 k m
k
Fall 2006 Costas Busch - RPI 25
x y za m!
y a , 1 k m
k

From the Pumping Lemma: xy z L


i

i 0, 1, 2, ...

Thus: xy z L
2

Fall 2006 Costas Busch - RPI 26


x y za m!
y a , 1 k m
k

From the Pumping Lemma: xy z L


2

mk m!m
xy z a...aa...aa...aa...aa...aa...a L
2

x y y z

Thus: m! k
a L
Fall 2006 Costas Busch - RPI 27
m! k
a L 1 k m

Since: L {a : n 0}
n!

There must exist p such that:

m! k p!

Fall 2006 Costas Busch - RPI 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
Fall 2006 Costas Busch - RPI 29
m! k 1 k m
a L

BUT: L {a : n 0}
n!

m! k
a L

CONTRADICTION!!!
Fall 2006 Costas Busch - RPI 30
Therefore: Our assumption that L
is a regular language is not true

Conclusion: L is not a regular language

END OF PROOF
Fall 2006 Costas Busch - RPI 31

You might also like