Abstract family of languages Created 2026-10-14 Updated 2026-11-05
An abstract family of languages is a family of formal languages containing a nonempty language and closed under finite union, concatenation of formal languages, positive closure of a formal language, nonerasing monoid homomorphisms between free word monoids, inverse homomorphisms, and intersection with regular languages. Here positive closure means , and nonerasing means that the homomorphism maps every alphabet letter to a nonempty word.
A full abstract family of languages allows arbitrary word homomorphisms, including ones that erase letters. This distinction matters: erasing an unbounded amount of a computation or derivation can change the resources needed to recognize the image language. The regular languages and context-free languages are full abstract families. In particular, the closure axioms say that if is context-free and is regular, then is context-free; they do not assert closure under intersection of two arbitrary context-free languages. The framework collects the common constructions without identifying the different language classes.[ref]
Context-free language Created 2026-09-24 Updated 2026-11-05
A context-free language is a formal language generated by a context-free grammar, in which each production has exactly one nonterminal on its left side. Equivalently, it is recognized by a nondeterministic pushdown automaton.
For example, the grammar generates . A derivation adds one matching pair at a time, while the empty production stops the process. The language is not regular: matching the two unbounded counts requires more memory than a finite-state recognizer provides. Context-free languages describe many nested structures, including balanced delimiters and recursive expression syntax.
Context-sensitive grammar 2026-11-05
A context-sensitive grammar has productions of the form , where is a nonterminal symbol and is a nonempty word. The surrounding words specify the context in which replacement is permitted. Every such step is length-nondecreasing.
An equivalent language-class description uses arbitrary noncontracting production rules with and a nonterminal in . If the empty word is included, the customary exception is with start symbol absent from every right side. Individual noncontracting rules need not have the displayed context-preserving form, although the generated language classes agree.
For example, replaces only when its immediate context is on the left and on the right. The language is context-sensitive and is not a context-free language. The associated computational model is a linear bounded automaton, whose usable tape is bounded by a constant times input length.
CYK algorithm 2026-10-03
The CYK algorithm decides membership in a context-free language given by a grammar in Chomsky normal form. It records, for every substring, the nonterminals that derive that substring and combines adjacent substrings using binary productions. For a word of length and a fixed grammar, it runs in time.
A full abstract family of languages is an abstract family of languages closed under all word monoid homomorphisms, including those erasing letters. It retains the other closure requirements: finite union, concatenation of formal languages, positive closure of a formal language, inverse homomorphism, and intersection with regular languages.
For example, the homomorphism , sends to . Such a map is excluded by a nonerasing-only homomorphism axiom. The adjective full says this additional erasure operation is allowed; it does not assert closure under every operation on languages.
Both regular languages and context-free languages form full abstract families. For the latter, intersection with a regular language is allowed, but intersection of two arbitrary context-free languages need not remain context-free. Erasing an arbitrarily long part of a representation can conceal unbounded intermediate work, so the distinction matters when comparing computational language classes.[ref]
This formal language is not a context-free language. For pumping length , use . A pumpable window of length at most cannot meet both outer blocks. If pumping adds copies of , then and . Preserving the product constraint would require , impossible both when and when it is positive. This contradicts the pumping lemma for context-free languages.
Nested-count context-free grammar Created 2026-09-24 Updated 2026-11-05
A context-free grammar can enforce several matched counts by nesting their dependencies. For example,
generates the context-free language . Applying the first recursive production rule times places zeros at both ends. Applying the second recursive production rule times places ones before the inner block and further zeros after it. Thus
Every terminal grammar derivation has this form, because it must switch from to exactly once. The nesting is useful: the final block records the sum of two independently chosen counts without requiring a context-sensitive grammar.
The formal language is not a context-free language. Suppose otherwise, and let be a pumping length from the pumping lemma for context-free languages. Choose
This word belongs to the formal language, since its middle exponent is the product of the two outer exponents. The pumping lemma for context-free languages would give
with in the formal language for every integer .
Let be the respective numbers of symbols in the two pumped pieces together. The window cannot contain both an and a : it would have to contain the entire middle block of length , plus at least those two outer symbols, exceeding . Hence
Pump once extra, taking . The resulting symbol counts are , , and . A necessary condition for membership, regardless of whether the block order survives, is
where was used.
If , then , contradicting that equality. If , then
again contradicting it. Thus every permissible decomposition fails at . This contradicts the pumping lemma for context-free languages and proves the claim. The obstruction is the multiplicative block-count language: a bounded local change cannot preserve the product constraint.
The formal language is a context-free language. A context-free grammar with start nonterminal symbol is
The production rule for nests one on the left and one on the right on each recursive use, so generates exactly for . Similarly, generates exactly for . The start production rule concatenates these words, yielding
Conversely, every choice of nonnegative integers is achieved by using the recursive production rules exactly times before their epsilon productions. Hence this context-free grammar generates precisely the required formal language, including all cases where either count is zero.
Let a deterministic finite automaton recognizing the regular language have states , start state , accepting states , and transition function . Construct a context-free grammar with one nonterminal for every state, start symbol , and productions
Induction on the length of a word shows that derives exactly when the automaton reaches from after reading . The terminal production can then end the derivation precisely at an accepting state. Thus the grammar generates exactly the recognized language, proving every regular language is a context-free language. This is actually a right-linear grammar, a special case of a context-free grammar.
Treat the fixed letters , the empty-language and empty-word symbols, and the punctuation of expressions as a finite token alphabet. In the usual syntax allowing parentheses, union, concatenation, and star, the following context-free grammar generates exactly the syntactically valid regular expressions:
Structural induction proves that every generated string is an expression and that every expression has a derivation. Grammar ambiguity does not affect the context-free language assertion.
If the language of these expressions were a regular language, its intersection with the regular token language consisting of some opening parentheses, then , then some closing parentheses would be regular. That intersection is exactly
The pumping lemma for regular languages contradicts regularity: a sufficiently long opening-parenthesis prefix forces a pumpable segment wholly within that prefix, and pumping it changes the two parenthesis counts unequally. Hence the expression syntax is context-free but not regular. This conclusion concerns the strings describing expressions, not the languages those expressions denote; it uses the usual concrete syntax with arbitrary nested parentheses.
Use . A halting algorithm checks that a word consists of three consecutive blocks in the correct order and compares their lengths, so is a decidable language. If it were a context-free language, apply the pumping lemma for context-free languages to . The segment containing both pumped pieces has length at most , so it cannot meet both the and blocks. Pumping down therefore changes at least one block count but leaves another equal to , or destroys the required block order. Either way the resulting word is not in , a contradiction. Thus is a decidable language but not a context-free language.
Use . The context-free grammar generates exactly , so it is a context-free language. It is not a regular language: if is a pumping length, any allowed decomposition of has a nonempty pumped segment consisting only of 's. Pumping down leaves fewer 's than 's, contradicting the pumping lemma for regular languages. Thus is a context-free language but not a regular language.
In strict Chomsky normal form, every production of a context-free grammar is or , with nonterminal symbols and a terminal symbol. Such a derivation cannot produce the empty word: it starts with one nonterminal symbol, and every step either increases the symbol count or replaces one symbol by one symbol. The context-free language , generated by , is therefore not generated by any strict CNF grammar.
The convention matters: extended Chomsky normal form permits with excluded from right-hand sides. Under that convention every context-free language has such a grammar, so the requested example would not exist.
The context-free languages and have context-free grammars , , , and , , , respectively.
Their intersection is . Suppose satisfied the pumping lemma for context-free languages with length . In a decomposition with and , the window cannot meet both the and blocks. Pumping down changes at least one count and leaves at least one count unchanged. Thus the three counts are unequal, or the word order is invalid, contrary to the pumping lemma for context-free languages. Hence CFLs are not closed under intersection.
Context-free languages are closed under union: use a new start symbol with alternatives for two renamed context-free grammars. If they were closed under complement in , De Morgan's laws would give
contradicting the preceding intersection example. Therefore some CFL has a non-context-free complement. This is an existence argument; it does not assert that both complements of the particular are non-context-free.
A concrete choice is . Words outside form a regular language. Among words inside it, membership in means the first two counts or the last two counts differ. Each unequal-count comparison has a context-free grammar: for with , use , ; for , replace by . Append any number of 's, or prefix any number of 's for the analogous comparison. Taking these unions gives a context-free language whose complement is the non-context-free equal-three-count language. These productions are definitions of the example, not a restriction to strict Chomsky normal form.
The pumping lemma for context-free languages states that every context-free language has a pumping length such that every with can be written
with , , and for every integer .
The pumping lemma for context-free languages states that for every context-free language there is a pumping length such that every with can be written
with
The language is not context-free. Suppose it had pumping length in the pumping lemma for context-free languages, and apply the lemma to . Write with , , and for every .
Let and be the respective numbers of s and s in . If , pumping with or destroys equality of the two block lengths. Hence a valid decomposition would require . Pumping with would then produce , where . But
so is not a square number. This contradiction proves the square-count language is not context-free.
A context-free grammar is a quadruple consisting of a finite set of nonterminal symbols, a disjoint finite alphabet of terminal symbols, a start symbol , and a finite set of productions with and . A sentence is a terminal word over an alphabet with , and the generated formal language is .
The first language is context-free. For example, the productions
generate exactly : each recursive production adds two s to the left and two s to the right.