Chomsky–Schützenberger representation theorem
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  formula_1 which maps symbols from an alphabet formula_2 to words over another alphabet formula_3; If the domain of this function is extended to words over formula_2 in the natural way, by letting formula_5 for all words formula_6 and formula_7, this yields a "homomorphism" formula_8. A "matched alphabet" formula_9 is an alphabet with two equal-sized sets; it is convenient to think of it as a set of parentheses types, where formula_10 contains the opening parenthesis symbols, whereas the symbols in formula_11 contains the closing parenthesis symbols. For a matched alphabet formula_9, the "Dyck language" formula_13 is given by Chomsky–Schützenberger  theorem. A language "L" over the alphabet formula_3 is context-free if and only if there exists Proofs of this theorem are found in several textbooks, e.g. or .