SFWRENG 2FA3 Lecture Notes - Lecture 4: Pumping Lemma, Regular Language, Postal Codes In Canada

• School: McMaster University
• Department: Software Engineering
• Course: SFWRENG 2FA3
• Professor: N A

Document Summary

Regular language: a language, a, is regular if and only if an fsa, , , such that l( ) = a. Membership algorithm: for a language, a, an algorithm, alg, is a membership algorithm for a, such that for all * if a => yes. Our working memory in fsas is the set of states. The pumping lemma: if an infinite language, a, is regular, k u v w i s i x y z a y xuvwz a y u v w x y z. Applications of the pumping lemma: to prove that a given language is. No limitation on n. n m n. By pumping lemma, k > 0, u v w. Let z = , y = x y z a y u v w x u v v w z a kb , x = ka i s i i.