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. Specifically, the pumping lemma says that for any regular language formula_1 there exists a constant formula_2 such that any string formula_3 in formula_1 with length at least formula_2 can be  split into three substrings formula_6, formula_7 and formula_8 (formula_9, with formula_7 being non-empty), such that the strings formula_11 constructed by repeating formula_7 zero or more times are still in formula_1. This process of repetition is known as "pumping". Moreover, the pumping lemma guarantees that the length of formula_14 will be at most formula_2, imposing a limit on the ways in which formula_3 may be split. Finite languages vacuously satisfy the pumping lemma by having formula_2 equal to the maximum string length in formula_1 plus one. The pumping lemma is useful for disproving the regularity of a specific language in  question. It 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. Let formula_1 be a regular language. Then there exists an integer formula_20 depending only on formula_1 such that every string formula_3 in formula_1 of length at least formula_2 (formula_2 is called the "pumping length") can be written as formula_9 (i.e., formula_3 can be divided into three substrings), satisfying the following conditions: formula_7 is the substring that can be  pumped (removed or repeated any number of times, and the resulting string is always in formula_1). (1) means the loop formula_7 to be pumped must be of length at least one; (2) means the loop must occur within the first formula_2 characters. formula_35 must be smaller than formula_2 (conclusion of (1) and (2)), but apart from that, there is no restriction on formula_6 and formula_8. In simple words, for any regular language formula_1, any sufficiently long string formula_3 (in formula_1) can be split into 3 parts. i.e. formula_9 , such that all the strings formula_43 for formula_44 are also in formula_1 . Below is a formal expression of the Pumping Lemma. formula_46 Use of the lemma. 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. For example, the language formula_47 over the alphabet formula_48 can be shown to be non-regular as follows: Let formula_49, and formula_50 be as used in the formal statement for the pumping lemma above. Assume that some constant formula_2 exists as required by the lemma . Let formula_3 in formula_1 be given by formula_54, which is a string longer than formula_2. By the pumping lemma, there must exist a decomposition formula_9 with formula_57 and formula_58 such that formula_59 in formula_1 for every formula_61. Since formula_57, the string formula_7 only consists of instances of formula_64. Moreover, because formula_58, it contains at least one instance of the letter formula_64. However, formula_67 has more instances of the letter formula_64 than the letter formula_69, since some instances of formula_64 but none of formula_69 were added. Therefore, formula_67 is not in formula_1 which contradicts the Pumping lemma. Therefore, formula_1 can not  be regular. The proof that the language of balanced (i.e., properly nested) parentheses is not regular follows the same idea. Given formula_2, there is a string of balanced parentheses that begins with more than formula_2 left parentheses, so that formula_7 will consist entirely of left parentheses. By repeating formula_7, 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 (FSA) that accepts the language. The number of states in such an  FSA are counted and that count is used as the pumping length formula_2. For a string of length at least formula_2, let formula_81 be the start state and let formula_82 be the sequence of the next formula_2 states visited as the string is emitted. Because the FSA has only formula_2 states, within this sequence of formula_85 visited states there must be at least one state that is repeated. Write formula_86 for such a state. The transitions that take the machine from the first encounter of state formula_86 to the second encounter of state formula_86 match some string. This string is  called formula_7 in the lemma, and since the machine will match a string without the formula_7 portion, or with the string formula_7 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, 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 formula_92 is a repeated state. Since the  substring bc takes the machine through transitions that start at state formula_92 and end at state formula_92, 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 is broken into an formula_6 portion a, a formula_7 portion bc and a formula_8 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 formula_1 is regular, then there exists a number formula_20 (the pumping length) such that every string formula_100 in formula_1 with formula_102 can be written in the form with strings formula_6, formula_7 and formula_8 such that formula_107, formula_108 and From this, the above standard version follows a special case, with both formula_112 and formula_113 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. Converse of lemma not true. 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: In other words, formula_1 contains all strings over the alphabet formula_116 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 formula_117. 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. 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.