View source for Pumping lemma for regular languages

{{Short description|Lemma that defines a property of regular languages}}
[[File:Pumping Lemma for regular languages diagram.png|400px|thumb|right|For every long enough string in a regular language, there must be a middle section (<math>y</math>) that can be repeated (or pumped) any number of times to produce a string still in the language.]]

In the theory of [[formal language]]s, the '''pumping lemma for regular languages''' is a [[Lemma (mathematics)|lemma]] that describes an essential property of all [[regular language]]s. Informally, it says that all sufficiently long [[string (computer science)|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.

Specifically, the pumping lemma says that for any regular language <math>L</math>, there exists a constant <math>p</math> such that any string <math>w</math> in <math>L</math> with length at least <math>p</math> can be split into three substrings <math>x</math>, <math>y</math> and <math>z</math> ({{nowrap begin}}<math>w = xyz</math>{{nowrap end}}, with <math>y</math> being non-empty), such that the strings <math>xz, xyz, xyyz, xyyyz, ...</math> are also in <math>L</math>. The process of repeating <math>y</math> zero or more times is known as "pumping". Moreover, the pumping lemma guarantees that the length of <math>xy</math> will be at most <math>p</math>, thus giving a "small" substring <math>xy</math> that has the desired property. 

Languages with a finite number of strings [[vacuous truth|vacuously]] satisfy the pumping lemma by having <math>p</math> equal to the maximum string length in <math>L</math> plus one. By doing so, zero strings in <math>L</math> have length greater than <math>p</math>.

The pumping lemma was first proven by [[Michael O. Rabin|Michael Rabin]] and [[Dana Scott]] in 1959,<ref>{{cite journal|last1=Rabin |first1=Michael |authorlink1=Michael O. Rabin|last2=Scott |first2=Dana |authorlink2=Dana Scott  |date=Apr 1959 |title=Finite Automata and Their Decision Problems |journal=IBM Journal of Research and Development |volume=3 |issue=2 |pages=114–125 |url=http://www.cse.chalmers.se/~coquand/AUTOMATA/rs.pdf |doi=10.1147/rd.32.0114 |url-status=unfit |archiveurl=https://web.archive.org/web/20101214122150/http://www.cse.chalmers.se/~coquand/AUTOMATA/rs.pdf |archivedate=December 14, 2010 }} Here: Lemma 8, p.119</ref> 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]].<ref>{{citation
 | last1 = Bar-Hillel | first1 = Y. | author1-link = Yehoshua Bar-Hillel
 | last2 = Perles | first2 = M.
 | last3 = Shamir | first3 = E. | author3-link = Eli Shamir
 | issue = 2
 | journal = Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung
 | pages = 143–172
 | title = On formal properties of simple phrase structure grammars
 | volume = 14
 | year = 1961
}}</ref><ref>{{cite book
 |author1=John E. Hopcroft |author2=Rajeev Motwani |author3=Jeffrey D. Ullman | title=Introduction to Automata Theory, Languages, and Computation
 | year=2003
 | publisher=Addison Wesley
}} Here: Sect.4.6, p.166</ref>

== Formal statement ==
Let <math>L</math> be a regular language. Then there exists an integer <math>p \geq 1</math> depending only on <math>L</math> such that every string <math>w</math> in <math>L</math> of length at least <math>p</math> (<math>p</math> is called the "pumping length")<ref name=BLRS86>{{cite book | last1=Berstel | first1=Jean | last2=Lauve | first2=Aaron | last3=Reutenauer | first3=Christophe | last4=Saliola | first4=Franco V. | title=Combinatorics on words. Christoffel words and repetitions in words | series=CRM Monograph Series | volume=27 | location=Providence, RI | publisher=[[American Mathematical Society]] | year=2009 | isbn=978-0-8218-4480-9 | zbl=1161.68043 | page=86}}</ref> can be written as <math>w = xyz</math> (i.e., <math>w</math> can be divided into three substrings), satisfying the following conditions:

# <math> |y| \geq 1 </math>
# <math> |xy| \leq p </math>
# <math> (\forall n \geq 0) ( xy^nz \in L )</math>

<math>y</math> is the substring that can be pumped (removed or repeated any number of times, and the resulting string is always in <math>L</math>). (1) means the loop <math>y</math> to be pumped must be of length at least one, that is, not an empty string; (2) means the loop must occur within the first <math>p</math> characters. <math>|x|</math> must be smaller than <math>p</math> (conclusion of (1) and (2)), but apart from that, there is no restriction on <math>x</math> and <math>z</math>.

In simple words, for any regular language <math>L</math>, any sufficiently long string <math>w</math> (in <math>L</math>) can be split into 3 parts, i.e. <math>w = xyz</math>, such that all the strings <math>xy^nz</math> for <math>n \geq 0</math> are also in <math>L</math>.

Below is a formal expression of the pumping lemma.

<math>
\begin{array}{l}
\forall L\subseteq \Sigma^*, \mbox{regular}(L) \implies \\
\quad \exists p\geq 1, \forall w\in L, |w|\geq p \implies \\
\qquad \exists x,y,z \in \Sigma^*, (w=xyz) \land (|y|\geq 1) \land (|xy|\leq p) \land (\forall n\geq 0, xy^nz\in L)
\end{array} 
</math>

== 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.

<blockquote>
Example: The language <math>L = \{a^n b^n : n \geq 0\}</math> over the alphabet <math>\Sigma = \{a, b\}</math> can be shown to be non-regular as follows:

# Assume that some constant <math>p \geq 1</math> exists as required by the lemma. 
# Let <math>w</math> in <math>L</math> be given by <math>w = a^p b^p</math>, which is a string longer than <math>p</math>. 
# By the pumping lemma, there must exist a decomposition <math>w = xyz</math> with <math>|xy| \leq p</math> and <math>|y| \geq 1</math> such that <math>xy^iz</math> in <math>L</math> for every <math>i \geq 0</math>. 
# Since <math>|xy| \leq p</math>, the string <math>y</math> only consists of instances of <math>a</math>.  
# Because <math>|y| \geq 1</math>, it contains at least one instance of the letter <math>a</math>. 
# Pumping <math>y</math> to give <math>xy^2z</math> gives a word with more instances of the letter <math>a</math> than the letter <math>b</math>, since  some instances of <math>a</math> but none of <math>b</math> were added. 
# Therefore, <math>xy^2z</math> is not in <math>L</math> which contradicts the pumping lemma.
# Therefore, <math>L</math> cannot be regular.
</blockquote>

The proof that the [[Dyck language|language of balanced (i.e., properly nested) parentheses]] is not regular follows the same idea.  Given <math>p</math>, there is a string of balanced parentheses that begins with more than <math>p</math> left parentheses, so that <math>y</math> will consist entirely of left parentheses.  By repeating <math>y</math>, 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 ==

[[File:Pumping-Lemma_xyz_svg.svg|thumb|400px|Proof idea: Whenever a sufficiently long [[string (formal languages)|string]] ''xyz'' is recognized by a [[finite automaton#Mathematical model|finite automaton]], it must have reached some state (<math>q_s = q_t</math>) twice. Hence, after repeating ("pumping") the middle part <math>y</math> arbitrarily often (''xyyz'', ''xyyyz'', ...) the string will still be recognized.]]
For every regular language there is a [[finite-state automaton]] (FSA) that accepts the language.  The number of states in such an FSA are counted and that count is used as the pumping length <math>p</math>. For a string of length at least <math>p</math>, let <math>q_0</math> be the start state and let <math>q_1, ..., q_p</math> be the sequence of the next <math>p</math> states visited as the string is emitted.  Because the FSA has only <math>p</math> states, within this sequence of <math>p+1</math> visited states there must be at least one state that is repeated.  Write <math>q_s</math> for such a state.  The transitions that take the machine from the first encounter of state <math>q_s</math> to the second encounter of state <math>q_s</math> match some string.  This string is called <math>y</math> in the lemma, and since the machine will match a string without the <math>y</math> portion, or with the string <math>y</math> repeated any number of times, the conditions of the lemma are satisfied.

For example, the following image shows an FSA.

[[File:An automat accepting the language a(bc)*d.svg]]

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]] indicates that there must be at least one repeated state among the start state and the next four visited states.  In this example, only <math>q_1</math> is a repeated state.  Since the substring '''bc''' takes the machine through transitions that start at state <math>q_1</math> and end at state <math>q_1</math>, that portion could be repeated and the FSA would still accept, giving the string {{not a typo|'''abcbcd'''}}.  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''' is broken into an <math>x</math> portion '''a''', a <math>y</math> portion '''bc''' and a <math>z</math> 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 ==
If a language <math>L</math> is regular, then there exists a number <math>p \geq 1</math> (the pumping length) such that every string <math>uwv</math> in <math>L</math> with <math>|w| \ge p</math> can be written in the form 
:<math>uwv = uxyzv</math>
with strings <math>x</math>, <math>y</math> and <math>z</math> such that <math>|xy| \le p</math>, <math>|y| \ge 1</math> and
:<math>uxy^izv</math> is in <math>L</math> for every integer <math>i \geq 0</math>.<ref>{{cite book |last1=Savitch |first1=Walter |year=1982 |title=Abstract Machines and Grammars |isbn=978-0-316-77161-0 |page=[https://archive.org/details/abstractmachines0000savi/page/49 49] |publisher=Little, Brown |url=https://archive.org/details/abstractmachines0000savi/page/49 }}</ref>
From this, the [[#Formal statement|above]] standard version follows a special case, with both <math>u</math> and <math>v</math> 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 and sufficient condition|''necessary'' but not ''sufficient'' condition]] for a language to be regular.

For example, consider the following language:
:<math>\begin{matrix}L & = & \{uvwxy : u,y \in \{0,1,2,3\}^*; v,w,x \in \{0,1,2,3\} \land (v=w \lor v=x \lor x=w)\} \\ & & \cup \ \{w : w \in \{0,1,2,3\}^*\land \text {precisely } \tfrac 1 7 \text{ of the characters in }w \text{ are 3's}\}\end{matrix}</math>.
In other words, <math>L</math> contains all strings over the alphabet <math>\{0,1,2,3\}</math> with a substring of length 3 including a duplicate character, as well as all strings over this alphabet where precisely 1/7 of the string's characters are 3's. This language is not regular but can still be "pumped" with <math>p = 5</math>. Suppose some string ''s'' has length at least 5. Then, since the alphabet has only four characters, at least two of the first five characters in the string must be duplicates. They are separated by at most three characters.
* If the duplicate characters are separated by 0 characters, or 1, pump one of the other two characters in the string, which will not affect the substring containing the duplicates.
* If the duplicate characters are separated by 2 or 3 characters, pump 2 of the characters separating them. Pumping either down or up results in the creation of a substring of size 3 that contains 2 duplicate characters.
* The second condition of <math>L</math> ensures that <math>L</math> is not regular: Consider the string <math>(013)^{3m}(012)^i</math>. This string is in <math>L</math> exactly when <math>i=4m</math> and thus <math>L</math> is not regular by the [[Myhill–Nerode theorem]].

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 ==
* [[Ogden's lemma]]
* [[Pumping lemma for context-free languages]]
* [[Pumping lemma for regular tree languages]]

== Notes ==
<references/>

== References ==
* {{cite book | last=Lawson | first=Mark V. | title=Finite automata | publisher=Chapman and Hall/CRC | year=2004 | isbn=978-1-58488-255-8 | zbl=1086.68074 }}
* {{cite book | first=Michael | last=Sipser | authorlink=Michael Sipser | year=1997 | title=Introduction to the Theory of Computation | publisher=PWS Publishing | isbn=978-0-534-94728-6 | zbl=1169.68300 | chapter=1.4: Nonregular Languages | pages=[https://archive.org/details/introductiontoth00sips/page/77 77–83] | title-link=Introduction to the Theory of Computation }}
* {{cite book | first1=John E. | last1=Hopcroft | author1-link=John Hopcroft | first2=Jeffrey D. | last2=Ullman | author2-link=Jeffrey Ullman | title=Introduction to Automata Theory, Languages, and Computation | publisher=Addison-Wesley Publishing | location=Reading, Massachusetts | year=1979 | isbn=978-0-201-02988-8 | zbl=0426.68001 | title-link=Introduction to Automata Theory, Languages, and Computation }} ''(See chapter 3.)''
* {{cite book|author1=Bakhadyr Khoussainov|author2=Anil Nerode|authorlink2=Anil Nerode|title=Automata Theory and its Applications|url=https://books.google.com/books?id=wR_oBwAAQBAJ|date=6 December 2012|publisher=Springer Science & Business Media|isbn=978-1-4612-0171-7}}

{{Formal languages and grammars |state=collapsed}}

[[Category:Formal languages]]
[[Category:Lemmas]]
[[Category:Finite-state machines]]

[[de:Pumping-Lemma#Reguläre Sprachen]]