Pumping lemma for regular languages

A theorem stating that every sufficiently long string in a regular language can be split into three parts so that repeating the middle part any number of times preserves membership.

Finite automaton: A computational model with finitely many states that recognizes strings by changing states as it reads symbols. A regular language is recognized by a finite automaton, whose bounded states force the repetition.
Nonregular language: A formal language that cannot be recognized by any finite automaton. Contradicting the lemma’s required decomposition establishes nonregularity.
Formal language: A set of finite strings over a specified alphabet. The theorem concerns membership of strings in such a set.
Closure properties of regular languages: The operations under which regular languages remain regular, including union, intersection, and complement. Closure arguments often prove nonregularity without relying on pumping decompositions.
Pigeonhole principle: A counting principle stating that placing more objects than containers guarantees at least one container holds multiple objects. A long accepting run visits some state more than once, creating a repeatable segment.
Pumping lemma for context-free languages: A theorem requiring sufficiently long strings in context-free languages to have a decomposition with repeatable sections. Its multiple pumped sections address a stronger language family than the regular-language lemma.
String (computer science): A finite sequence of symbols drawn from an alphabet. The lemma divides one sufficiently long string into three consecutive parts.
Regular-language closure under homomorphism: The property that replacing each symbol consistently in a regular language preserves regularity. Homomorphisms can transfer a known nonregularity result to another language.
Automaton state: A condition of a finite automaton that determines how it processes subsequent input. The repeated state marks the endpoints of the substring that can be pumped.
Context-free language: A language generated by a context-free grammar or recognized by a pushdown automaton. The regular-language lemma does not prove a language non-context-free; that requires stronger tools.

Linked from 7 pages