Class Notes (809,497)
Canada (493,753)
CPSC 313 (6)

The Pumping Lemma

1 Page
Unlock Document

University of Calgary
Computer Science
CPSC 313
Philipp Woelfel

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

Log In


Don't have an account?

Join OneClass

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

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.