In the theory of formal languages, the pumping lemma for regular languages describes an essential property of all regular languages. Informally, it says that all sufficiently long words in a regular language may be pumped — that is, have a middle section of the word repeated an arbitrary number of times — to produce a new word which also lies within the same language.
Specifically, the pumping lemma says that for any regular language L there exists a constant p such that any word w in L with length at least p can be split into three substrings, w = xyz, where the middle portion y must not be empty, such that the words xz, xyz, xyyz, xyyyz, … constructed by repeating y an arbitrary number of times (including zero times) are still in L. This process of repetition is known as "pumping". Moreover, the pumping lemma guarantees that the length of xy will be at most p, imposing a limit on the ways in which w may be split. Finite languages trivially satisfy the pumping lemma by having p equal to the maximum string length in L plus one.
The pumping lemma was first proved by Dana Scott and Michael Rabin in 1959. It was rediscovered shortly after by Yehoshua Bar-Hillel, Micha A. Perles, and Eli Shamir in 1961. It is useful for disproving the regularity of a specific language in question. It is one of a few pumping lemmas, each with a similar purpose.
Read more about Pumping Lemma For Regular Languages: Formal Statement, Use of Lemma, Proof of The Pumping Lemma, General Version of Pumping Lemma For Regular Languages, Converse of Lemma Not True, See Also
Famous quotes containing the words pumping, regular and/or languages:
“It is by teaching that we teach ourselves, by relating that we observe, by affirming that we examine, by showing that we look, by writing that we think, by pumping that we draw water into the well.”
—Henri-Frédéric Amiel (1821–1881)
“This is the frost coming out of the ground; this is Spring. It precedes the green and flowery spring, as mythology precedes regular poetry. I know of nothing more purgative of winter fumes and indigestions. It convinces me that Earth is still in her swaddling-clothes, and stretches forth baby fingers on every side.”
—Henry David Thoreau (1817–1862)
“The trouble with foreign languages is, you have to think before your speak.”
—Swedish proverb, trans. by Verne Moberg.