Class Notes
(809,497)

Canada
(493,753)

University of Calgary
(6,032)

Computer Science
(115)

CPSC 313
(6)

Philipp Woelfel
(6)

Lecture

# The Pumping Lemma

Unlock Document

University of Calgary

Computer Science

CPSC 313

Philipp Woelfel

Winter

Description

January 27th, 2012
Proof of the Pumping Lemma
Proof. Let L be regular and M = (Q;▯;▯;q ;F) be0a DFA for L.
Let the states in Q be q ;0::;q n▯1 .
Choose m := n + 1 = jQj + 1.
Consider an arbitrary w 2 L, such that jwj ▯ m.
Let the sequence of states that the DFA visits while processing w be
q0;q iq ;i::;q i
1 2 k
Among the ▯rst m + 1 > jQj states visited, there is some state that is repeated.
There is a state q = q = q ;z ▯ m, so that M visits states.
ir iz
q0;q 1q ;2::;q ;r::;q ;z::;q ik
Let x be the pre▯x of w that is processed until q is reached for the ▯rst time, and
xy the pre▯x until q is reached for the second time.
Then jyj ▯ 1 and jxyj ▯ m, and
▯ ▯
▯ = q = ▯ (q;y) and
▯ ▯
▯ = ▯ (q;z) 2 F.
! ▯ (q;y ) = q for any i ▯ 0.
▯ i

More
Less
Related notes for CPSC 313