In formal language theory, the Chomsky–Schützenberger representation theorem is a theorem derived by Noam Chomsky and Marcel-Paul Schützenberger about representing a given context-free language in terms of two simpler languages. These two simpler languages, namely a regular language and a Dyck language, are combined by means of an intersection and a homomorphism.
A few notions from formal language theory are in order. A context-free language is regular, if can be described by a regular expression, or, equivalently, if it is accepted by a finite automaton. A homomorphism is based on a function h which maps symbols from an alphabet Γ to words over another alphabet Σ ; If the domain of this function is extended to words over Γ in the natural way, by letting h ( x y ) = h ( x ) h ( y ) for all words x and y , this yields a homomorphism h : Γ ∗ → Σ ∗ . A matched alphabet T ∪ T ¯ is an alphabet with two equal-sized sets; it is convenient to think of it as a set of parentheses types, where T contains the opening parenthesis symbols, whereas the symbols in T ¯ contains the closing parenthesis symbols. For a matched alphabet T ∪ T ¯ , the Dyck language D T is given by
D T = { w ∈ ( T ∪ T ¯ ) ∗ ∣ w is a correctly nested sequence of parentheses } words that are well-nested parentheses over T ∪ T ¯ .
Chomsky–Schützenberger theorem. A language
L over the alphabet
Σ is context-free if and only if there exists
a matched alphabet T ∪ T ¯ a regular language R over T ∪ T ¯ ,and a homomorphism h : ( T ∪ T ¯ ) ∗ → Σ ∗ such that
L = h ( D T ∩ R ) .
Proofs of this theorem are found in several textbooks, e.g. Autebert, Berstel & Boasson (1997) or Davis, Sigal & Weyuker (1994).
