More Applications Of The Pumping Lemma

More Applications of the Pumping Lemma

1

The Pumping Lemma: • Given a infinite regular language • there exists an integer • for any string • we can write • with

w∈ L

L

m

with length

| w|≥ m

w= x y z

| x y | ≤ m and | y | ≥ 1

• such that:

i

xy z ∈ L

i = 0, 1, 2, ... 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 integer in the Pumping Lemma

Pick a string

w

such that:

w∈ L length

We pick

and

| w|≥ m

m m m m

w=a b b a

6

Write

m m m m

a b b a =xyz

From the Pumping Lemma it must be that length | x

m

y | ≤ m, | y |≥ 1

m m m

xyz = a...aa...a...ab...bb...ba...a

x Thus:

y

z

k

y = a , k ≥1

7

k

m m m m

y = a , k ≥1

x y z=a b b a

From the Pumping Lemma:

i

xy z ∈ L i = 0, 1, 2, ...

Thus:

2

xy z ∈ L 8

k

m m m m

y = a , k ≥1

x y z=a b b a

From the Pumping Lemma:

2

xy z ∈ L

m m m

m+k 2

xy z = a...aa...aa...a...ab...bb...ba...a ∈ L

x Thus:

y a

y m+ k m m m

b b a

z

∈L 9

a BUT:

m+ k m m m

b b a

∈L

k ≥1

R

L = {vv : v ∈ Σ*}

a

m+ k m m m

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

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 Let

m

: n, l ≥ 0}

be the integer in the Pumping Lemma

Pick a string

w

such that:

w∈ L length

We pick

and

| w|≥ m

m m 2m

w=a b c

15

Write

m m 2m

a b c

=xyz

From the Pumping Lemma it must be that length | x

m

y | ≤ m, | y |≥ 1

m

2m

xyz = a...aa...aa...ab...bc...cc...c

x Thus:

y

z

k

y = a , k ≥1

16

m m 2m

x y z=a b c

From the Pumping Lemma:

k

y = a , k ≥1

i

xy z ∈ L i = 0, 1, 2, ...

Thus:

0

x y z = xz ∈ L 17

k

m m 2m

y = a , k ≥1

x y z=a b c

xz ∈ L

From the Pumping Lemma:

m−k

m

2m

xz = a...aa...ab...bc...cc...c ∈ L

x Thus:

z

a

m−k m 2m

b c

∈L 18

a

BUT:

m−k m 2m

b c

n l n +l

L = {a b c

a

m−k m 2m

b c

∈L

k ≥1

: n, l ≥ 0}

∉L

CONTRADICTION!!! 19

Therefore:

Our assumption that L is a regular language is not true

Conclusion: L

is not a regular language

20

Non-regular languages

n!

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 integer in the Pumping Lemma

Pick a string

w

such that:

w∈ L length

We pick

w=a

| w|≥ m

m! 24

Write

a

m!

=xyz

From the Pumping Lemma it must be that length | x

m xyz = a

m!

y | ≤ m, | y |≥ 1

m!−m

= a...aa...aa...aa...aa...a

x Thus:

y

z

k

y = a , 1≤ k ≤ m 25

x y z=a

k

m!

y = a , 1≤ k ≤ m

From the Pumping Lemma:

i

xy z ∈ L i = 0, 1, 2, ...

Thus:

2

xy z ∈ L 26

x y z=a

k

m!

y = a , 1≤ k ≤ m

From the Pumping Lemma:

m+k

2

xy z ∈ L

m!−m

2

xy z = a...aa...aa...aa...aa...aa...a ∈ L

x Thus:

y

y a

m!+ k

z

∈L

27

a Since:

m!+ k

∈L

1≤ k ≤ m

n!

L = {a : n ≥ 0}

There must exist

p

such that:

m!+ k = p! 28

However:

m!+ k ≤ m!+ m ≤ m!+ m! < m!m + m! = m!(m + 1) = (m + 1)!

for

m >1

m!+ k < (m + 1)! m!+ k ≠ p!

for any

p 29

a BUT:

m!+ k

∈L

1≤ k ≤ m

n!

L = {a : n ≥ 0}

a

m!+ k

∉L

CONTRADICTION!!! 30

Therefore:

Our assumption that L is a regular language is not true

Conclusion: L

is not a regular language

31