Global InformationPumping lemma for regular languages information
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,[1] 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.[2][3]
- ^ Rabin, Michael; Scott, Dana (Apr 1959). "Finite Automata and Their Decision Problems" (PDF). IBM Journal of Research and Development. 3 (2): 114–125. doi:10.1147/rd.32.0114. Archived from the original on December 14, 2010.
{{cite journal}}: CS1 maint: unfit URL (link) Here: Lemma 8, p.119 - ^ Bar-Hillel, Y.; Perles, M.; Shamir, E. (1961), "On formal properties of simple phrase structure grammars", Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung, 14 (2): 143–172
- ^ John E. Hopcroft; Rajeev Motwani; Jeffrey D. Ullman (2003). Introduction to Automata Theory, Languages, and Computation. Addison Wesley. Here: Sect.4.6, p.166