A context-free grammar is a quadruple consisting of finite nonterminal and terminal alphabets, a set of productions with one nonterminal on the left, and a start symbol . A context-free language is a language generated by such a grammar.
The pumping lemma for context-free languages says that there is a pumping length such that every in the language with can be written
with , , and in the language for every integer .
The language in (i) is not context-free. If it were, pump
The substring , having length at most , cannot meet both the - and -blocks. If pumping changes the number of 's or 's, those two counts cease to agree. If it changes neither, it changes the number of 's while the outer counts remain , so the middle count ceases to be . Every permitted decomposition therefore fails, contradicting the pumping lemma.
A type-2 rule is with one nonterminal on the left; a type-2 grammar and its language are context-free languages. The required repetition criterion is the pumping lemma for context-free languages.
No production introduces , so the two rules containing are unreachable. The effective derivations are
Thus the language is , which is not context-free language, although the displayed grammar itself also visibly has non-type-2 left sides.
Pushdown automaton 2026-10-31
A finite control equipped with an unbounded stack. A move reads one input symbol or the empty word, examines the top stack symbol, changes control state and replaces that top by a finite word over the stack alphabet. Nondeterministic choices give finitely many possible moves. With acceptance by final state and the entire input consumed, pushdown automata recognize exactly the context-free languages.
Seymour Ginsburg 2026-11-05
Seymour Ginsburg coauthored the 1969 studies of the abstract family of languages framework with Sheila Greibach and John Hopcroft. This approach compares formal-language classes through closure properties instead of one particular grammar or machine presentation.[ref]
For example, closure under intersection with regular languages permits restricting an existing language by a finite-state filter. That property is weaker than closure under arbitrary intersections: two context-free languages can have a non-context-free intersection. Stating the allowed operation precisely keeps a shared abstract framework from incorrectly identifying different language classes.
A context-free language recognized by scanning a string over the alphabet from right to left, counting 0 as and 1 as , and requiring every partial count to remain nonnegative. A context-free grammar with a unique parse tree for each generated string is , . To see uniqueness, reverse the strings: every nonempty nonnegative path either never returns to zero after its first step, or has a unique first return. These two cases determine the production and its component substrings.
Three-block context-free pumping obstruction Created 2026-09-24 Updated 2026-11-05
The pumping lemma for context-free languages rules out a formal language when two pumpable pieces cannot preserve all three linked block counts. For example, let . If were a context-free language with pumping length , the word would have a decomposition with and .
The window cannot contain both an and a , because the intervening block alone has length . Pumping down to therefore leaves at least one outer block at length , while deleting at least one symbol from another block. The remaining block counts cannot all be equal, so , contrary to the pumping lemma for context-free languages. This argument uses a necessary condition for context-free languages; satisfying a pumping condition would not itself prove that a formal language is a context-free language.
Every context-free language over a one-symbol alphabet is a regular language. Equivalently, the set of word lengths of a unary context-free language is ultimately periodic. This follows, for example, from the one-dimensional case of Parikh's theorem.