Class Notes (809,497)
CPSC 313 (6)
Lecture

# The Pumping Lemma

1 Page
103 Views

School
University of Calgary
Department
Computer Science
Course
CPSC 313
Professor
Philipp Woelfel
Semester
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

OR

Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.