Pumping lemma for context-free languages

A theorem stating that sufficiently long strings in any context-free language can be decomposed into five parts so two selected parts can be repeated together while the result remains in the language.

Context-free grammar: A formal grammar whose production rules replace one nonterminal at a time. The lemma applies to languages generated by these grammars.
Non-context-free language: A formal language that cannot be generated by any context-free grammar. A contradiction with the lemma can establish that a language lies outside the context-free class.
Pumping lemma for regular languages: A theorem requiring sufficiently long strings in a regular language to contain a repeatable substring. Its three-part decomposition reflects finite-automaton cycles rather than context-free parse-tree repetition.
Formal language: A set of finite strings over a specified alphabet. The theorem states a structural property of sets of strings.
Parse tree: A tree showing how grammar rules derive a string from a start symbol. Repeated nonterminals along a sufficiently deep parse path create the pumpable portions.
Context-free language: A language generated by a context-free grammar or recognized by a pushdown automaton. The theorem states a necessary property shared by every language in this class.
Closure properties of context-free languages: Rules describing which language operations preserve the context-free language class. Closure arguments often prove non-context-freeness where pumping alone cannot.
String (computer science): A finite sequence of symbols drawn from an alphabet. The lemma decomposes one sufficiently long string into five consecutive parts.
Chomsky normal form: A restricted grammar form whose rules produce two nonterminals or one terminal, with limited exceptions. Its branching structure helps bound parse-tree height in proofs of the lemma.
{aⁿbⁿcⁿ : n ≥ 0}: The language of strings containing equal numbers of a's, b's, and c's in that order. Its equal-count requirement makes it a standard target for a pumping-lemma contradiction.

Linked from 5 pages