Wikipedia / Pumping lemma for regular languages
Wikipedia / Pumping lemma for regular languages
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. The pumping lemma is useful for proving that a specific language is not a regular language, by showing that the language does not have the property.
( that has the desired property.
Languages with a finite number of strings vacuously.
The pumping lemma was first proven by Michael Rabin and Dana Scott in 1959, 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.
Formal statement
is called the "pumping length") can be divided into three substrings), satisfying the following conditions:
.
.
Below is a formal expression of the pumping lemma.
Use of the lemma to prove non-regularity
The pumping lemma is often used to prove that a particular language is non-regular: a proof by contradiction may consist of exhibiting a string (of the required length) in the language that lacks the property outlined in the pumping lemma.
can be shown to be non-regular as follows:
exists as required by the lemma.
.
.
.
.
were added.
which contradicts the pumping lemma.
cannot be regular.
The proof that the language of balanced (i.e., properly nested) parentheses, a string can be produced that does not contain the same number of left and right parentheses, and so they cannot be balanced.
Proof of the pumping lemma
For every regular language there is a finite-state automaton repeated any number of times, the conditions of the lemma are satisfied.
For example, the following image shows an FSA.
The FSA accepts the string: abcd. Since this string has a length at least as large as the number of states, which is four (so the total number of states that the machine passes through to scan abcd would be 5), the pigeonhole principle is a repeated state. Since the substring bc, that portion could be repeated and the FSA would still accept, giving the string . Alternatively, the bc portion could be removed and the FSA would still accept giving the string ad. In terms of the pumping lemma, the string abcd portion a portion bc portion d.
As a side remark, the problem of checking whether a given string can be accepted by a given nondeterministic finite automaton without visiting any state repeatedly, is NP hard.
General version of pumping lemma for regular languages
can be written in the form
and
.
From this, the above being the empty string.
Since the general version imposes stricter requirements on the language, it can be used to prove the non-regularity of many more languages.
Invalidity of the lemma converse
While the pumping lemma states that all regular languages satisfy the conditions described above, the converse of this statement is not true: a language that satisfies these conditions may still be non-regular. In other words, both the original and the general version of the pumping lemma give a necessary but not sufficient condition for a language to be regular.
For example, consider the following language:
.
All words in the language satisfy the condition of the pumping lemma:
to obtain a decomposition that satisfies the pumping lemma.
.
However, it can be shown, for instance with the Myhill–Nerode theorem is not regular.
The Myhill–Nerode theorem provides a test that exactly characterizes regular languages. The typical method for proving that a language is regular is to construct either a finite-state machine or a regular expression for the language.
See also
Notes
References
(See chapter 3.)