Pumping lemma
Encyclopedia
In the theory of formal language
s in computability theory
, a pumping lemma or pumping argument states that, for a particular language to be a member of a language class, any sufficiently long string in the language contains a section, or sections, that can be removed, or repeated any number of times, with the resulting string remaining in that language. The proofs of these lemmas typically require counting arguments such as the pigeonhole principle.
The two most important examples are the pumping lemma for regular languages
and the pumping lemma for context-free languages
. Ogden's lemma
is a second, stronger pumping lemma for context-free language
s.
These lemma
s can be used to determine if a particular language is not in a given language class. However, they cannot be used to determine if a language is in a given class, since satisfying the pumping lemma is a necessary, but not sufficient, condition for class membership.
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
s in computability theory
Computability theory
Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...
, a pumping lemma or pumping argument states that, for a particular language to be a member of a language class, any sufficiently long string in the language contains a section, or sections, that can be removed, or repeated any number of times, with the resulting string remaining in that language. The proofs of these lemmas typically require counting arguments such as the pigeonhole principle.
The two most important examples are the pumping lemma for regular languages
Pumping lemma for regular languages
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...
and the pumping lemma for context-free languages
Pumping lemma for context-free languages
The pumping lemma for context-free languages, also known as the Bar-Hillel lemma, is a lemma that gives a property shared by all context-free languages.- Formal statement :...
. Ogden's lemma
Ogden's lemma
In the theory of formal languages, Ogden's lemma provides an extension of flexibility over the pumping lemma for context-free languages....
is a second, stronger pumping lemma for context-free language
Context-free language
In formal language theory, a context-free language is a language generated by some context-free grammar. The set of all context-free languages is identical to the set of languages accepted by pushdown automata.-Examples:...
s.
These lemma
Lemma (mathematics)
In mathematics, a lemma is a proven proposition which is used as a stepping stone to a larger result rather than as a statement in-and-of itself...
s can be used to determine if a particular language is not in a given language class. However, they cannot be used to determine if a language is in a given class, since satisfying the pumping lemma is a necessary, but not sufficient, condition for class membership.