Ogden's lemma

Ogden's lemma is a pumping lemma for context-free languages that lets a proof mark positions in a string and constrain where a pumpable substring must occur.

Context-free grammar: A formal grammar whose productions replace one nonterminal with a string of terminals and nonterminals. 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. Ogden's lemma can prove that a candidate language lies outside the context-free family.
String decomposition: A representation of a string as an ordered concatenation of smaller substrings. The lemma guarantees a decomposition whose parts satisfy its pumping conditions.
Interchange lemma: A theorem for context-free languages that guarantees certain substrings can be exchanged across many strings. It offers a different structural constraint for proving properties of context-free languages.
Context-free language: A language generated by a context-free grammar, or equivalently recognized by a pushdown automaton. Ogden's lemma constrains sufficiently long strings in this language family.
Dyck language: A language of balanced strings of properly nested brackets, often used to study context-free structure. Its nested dependencies illustrate the kind of structure pumping arguments must preserve.
Concatenation: The operation of joining strings end to end to form a longer string. The pumped strings are formed by repeating or deleting designated substrings in a concatenation.
Ogden's pumping lemma for indexed languages: A pumping theorem for indexed languages, a class of languages more expressive than the context-free languages. The similarly named result concerns a stronger language class, not Ogden's lemma for context-free languages.
Parse tree: A tree representation of a grammar derivation, with nonterminals as internal nodes and produced symbols at the leaves. The pumping guarantee follows from repeated nonterminals along a sufficiently deep derivation path.
Intersection of context-free languages: The set of strings belonging to each of two or more context-free languages; it need not itself be context-free. Marking positions can expose dependencies that survive when a language combines multiple counting constraints.

Linked from 2 pages