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)
“They were regular in being gay, they learned little things that are things in being gay, they learned many little things that are things in being gay, they were gay every day, they were regular, they were gay, they were gay the same length of time every day, they were gay, they were quite regularly gay.”
—Gertrude Stein (1874–1946)
“People in places many of us never heard of, whose names we can’t pronounce or even spell, are speaking up for themselves. They speak in languages we once classified as “exotic” but whose mastery is now essential for our diplomats and businessmen. But what they say is very much the same the world over. They want a decent standard of living. They want human dignity and a voice in their own futures. They want their children to grow up strong and healthy and free.”
—Hubert H. Humphrey (1911–1978)