Formal Language, chapter 11, slide 23Copyright © 2007 by Adam Webber Pumping Lemma Structure Notice the alternating for all and there exist clauses: 1  L … 2  k … 3  xyz … 4  uvw … 5  i … Our proof showed how to construct the  parts But that isn t part of the lemma: it s a black box The lemma says only that k and uvw exist For all regular languages L there exists some integer k such that for all xyz  L with |y|  k, there exist uvw = y with |v| >0, such that for all i  0, xuv i wz  L.
{"Image DocumentName": "We have now encountered regular languages in several different places", "Image ImageDescription": "We have now encountered regular languages in several different places. They are the languages that can be recognized by a DFA. They are the languages that can be recognized by an NFA. They are the languages that can be denoted by a regular expression. They are the languages that can be generated by a right-linear grammar. You might begin to wonder: are there any languages that are not regular? In this chapter, we will see that there are. There is a proof tool that is often used to prove languages non-regular. It is called the pumping lemma, and it describes an important property that all regular languages have. If you can show that a given language does not have this property, you can conclude that it is not a regular language. Formal Language, chapter 11, slide 2.", "Image XResolution": "37", "Image YResolution": "37", "Image ResolutionUnit": "Pixels/Centimeter", "Image Software": "SlidePlayer", "Image YCbCrPositioning": "Centered"}