Essays /

15 Regular Pumping Lemma Examples Essay

Essay preview

More Applications
of
the Pumping Lemma
This ppt is the work by Dr. Costas Busch, used with permission, and available from
http://csc.lsu.edu/~busch/courses/theorycomp/fall2008/
1

The Pumping Lemma:
• Given a infinite regular language
L
• there exists an integerm

| w | m
with length

• for any string w L
• we can write w  x
• with

|x y|  m

• such that:
Fall 2006

(critical length

yz
and |

i

xy z  L
Costas Busch - RPI

y | 1

i 0, 1, 2, ...
2

Non-regular languages

R

L {vv : v  *}

Regular languages

Fall 2006

Costas Busch - RPI

3

Theorem:The language
R

L {vv : v  *}

 {a, b}

is not regular

Proof:

Fall 2006

Use the Pumping Lemma

Costas Busch - RPI

4

R

L {vv : v  *}
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

R

L {vv : v  *}
Let

m

be the critical length for L

Pick a string w

such that: w

 L

and length

We pick
Fall 2006

| w | m

m m m m

w a b b a
Costas Busch - RPI

6

From the Pumping ...

Read more

Keywords

/~busch/courses/theorycomp/fall2008/ 0 1 10 11 12 13 14 15 16 17 18 19 2 20 2006 21 22 23 24 25 26 27 28 29 2m 3 30 31 4 5 6 7 8 9 aa ab appli applic assum assumpt avail b ba bb bc busch c cc conclus contradict costa critic csc.lsu.edu csc.lsu.edu/~busch/courses/theorycomp/fall2008/ dr end exampl exist fall given howev infinit integerm k l languag lemma length let m must n non non-regular ofl p permiss pick ppt proof pump r regular rpi sinc string thatl theorem therefor thus true use v vv w work write x xy xyz xz y yz z