Pumping lemma for regular languages

In the theory of formal languages, the pumping lemma for regular languages is a lemma that describes an essential property of all regular languages. Informally, it says that all sufficiently long strings in a regular language may be pumped—that is, have a middle section of the string repeated an arbitrary number of times—to produce a new string that is also part of the language. Specifically, the pumping lemma says that for any regular language there exists a constant such that any string in with length at least can be split into three substrings , and (, with being non-empty), such that the strings constructed by repeating zero or more times are still in . This process of repetition is known as "pumping". Moreover, the pumping lemma guarantees that the length of will be at most , imposing a limit on the ways in which may be split. Languages with a finite number of strings vacuously satisfy the pumping lemma by having equal to the maximum string length in plus one. By doing so, zero strings in have length greater than . The pumping lemma is useful for disproving the regularity of a specific language in question. It was first proven by Michael Rabin and Dana Scott in 1959, and rediscovered shortly after by Yehoshua Bar-Hillel, Micha A. Perles, and Eli Shamir in 1961, as a simplification of their pumping lemma for context-free languages. Let be a regular language. Then there exists an integer depending only on such that every string in of length at least ( is called the "pumping length") can be written as (i.e., can be divided into three substrings), satisfying the following conditions: is the substring that can be pumped (removed or repeated any number of times, and the resulting string is always in ). (1) means the loop to be pumped must be of length at least one; (2) means the loop must occur within the first characters. must be smaller than (conclusion of (1) and (2)), but apart from that, there is no restriction on and . In simple words, for any regular language , any sufficiently long string (in ) can be split into 3 parts.