Formal languages | Lemmas | Finite automata
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 , 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. Finite languages vacuously satisfy the pumping lemma by having equal to the maximum string length in plus one. 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. (Wikipedia).
