Pumping lemma for regular languages

Common card · No. 327292

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. Specifically, the pumping lemma says that for any regular language L {\displaystyle L} , there exists a constant p {\displaystyle p} such that any string w {\displaystyle w} in L {\displaystyle L} with length at least p {\displaystyle p} can be split...

Read on Wikipedia · Image Epachamo, CC BY-SA 4.0