A proof technique used to show that a given language is not regular, or not context-free, by demonstrating that any sufficiently long string in the language can be split into parts that can be repeated, or pumped, in a way that produces a string outside the language.
Facts
Core PrincipleAny sufficiently long string in a regular language can have a middle section repeated any number of times and stay in the language. 1 Connections
Sources
1. Pumping lemma for regular languages - Wikipedia
Section: History
The pumping lemma was first proven by Michael Rabin and Dana Scott in 1959
Lead paragraph
have a middle section of the string repeated an arbitrary number of times
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.