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 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 that also lies within the same language. 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 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 that also lies within the same language. Specifically, the pumping lemma says that for any regular language L {displaystyle L} there exists a constant p {displaystyle p} such that any word w {displaystyle w} in L {displaystyle L} with length at least p {displaystyle p} can be split into three substrings, w = x y z {displaystyle w=xyz} , where the middle portion y {displaystyle y} must not be empty, such that the words x z , x y z , x y y z , x y y y z , . . . {displaystyle xz,xyz,xyyz,xyyyz,...} constructed by repeating y {displaystyle y} zero or more times are still in L {displaystyle L} . This process of repetition is known as 'pumping'. Moreover, the pumping lemma guarantees that the length of x y {displaystyle xy} will be at most p {displaystyle p} , imposing a limit on the ways in which w {displaystyle w} may be split. Finite languages vacuously satisfy the pumping lemma by having p {displaystyle p} equal to the maximum string length in L {displaystyle L} 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. Let L {displaystyle L} be a regular language. Then there exists an integer p ≥ 1 {displaystyle pgeq 1} depending only on L {displaystyle L} such that every string w {displaystyle w} in L {displaystyle L} of length at least p {displaystyle p} ( p {displaystyle p} is called the 'pumping length') can be written as w = x y z {displaystyle w=xyz} (i.e., w {displaystyle w} can be divided into three substrings), satisfying the following conditions: y {displaystyle y} is the substring that can be pumped (removed or repeated any number of times, and the resulting string is always in L {displaystyle L} ). (1) means the loop y {displaystyle y} to be pumped must be of length at least one; (2) means the loop must occur within the first p {displaystyle p} characters. | x | {displaystyle |x|} must be smaller than p {displaystyle p} (conclusion of (1) and (2)), but apart from that, there is no restriction on x {displaystyle x} and z {displaystyle z} . In simple words, for any regular language L {displaystyle L} , any sufficiently long word w {displaystyle w} (in L {displaystyle L} ) can be split into 3 parts.i.e. w = x y z {displaystyle w=xyz} , such that all the strings x y n z {displaystyle xy^{n}z} for n ≥ 0 {displaystyle ngeq 0} are also in L {displaystyle L} .