Chomsky–Schützenberger theorem

The theorem asserts that for any context-free language L over an alphabet Σ, there exists a Dyck language D_k (with k types of parentheses), a regular language R, and a homomorphism h such that L = h(D_k ∩ R).¹ The Dyck language captures nested structure, while the regular language enforces local constraints, and the homomorphism maps parentheses to the original alphabet. This decomposition is analogous to the representation of context-free languages as the yield of a context-free grammar in Chomsky normal form. The theorem was published in 1963 in the context of algebraic approaches to formal languages.²

The proof proceeds by converting a context-free grammar in Chomsky normal form into a pushdown automaton, then constructing a Dyck language and a regular language that simulate the automaton's stack behavior. The homomorphism erases the parentheses introduced by the simulation. A key idea is the use of the "parenthesis grammar" whose productions generate balanced parentheses for each rule, and then intersecting with a regular language that encodes the sequence of rules applied.¹ An alternative proof uses the algebraic characterization of context-free languages as the least fixed point of a matrix equation, leading to a representation via the Dyck language and a regular language.

The theorem has several important applications. It provides a method to show that context-free languages are closed under homomorphism, inverse homomorphism, and intersection with regular languages. It is used in the theory of parsing, particularly in the recognition of context-free languages via matrix multiplication algorithms. The representation also underlies the construction of tree automata for context-free grammars and the study of the Chomsky hierarchy. In computational linguistics, the theorem connects natural language syntax to algebraic structures.

While the theorem is often stated for context-free languages, it also holds for the class of languages generated by context-free grammars in a more general algebraic setting, such as those over a free monoid. The original paper by Chomsky and Schützenberger also introduced the concept of a "Dyck language" and established its central role in formal language theory. A less-known corollary is that every context-free language can be generated by a grammar with at most two nonterminals. The theorem has been extended to more powerful language classes, such as indexed languages, using multi-stack automata. The minimal number of parentheses types needed is related to the maximum number of nonterminals in the grammar.³

context-free language

A language generated by a context-free grammar, recognized by a pushdown automaton.

Dyck language

The language of all properly balanced strings of parentheses of a given number of types.

homomorphism

A function that maps each symbol in a string to a string over another alphabet, applied symbol by symbol.

regular language

A language recognized by a finite automaton, definable by a regular expression.