In formal language theory, the Chomsky–Schützenberger representation theorem is a theorem derived by Noam Chomsky and Marcel-Paul Schützenberger in 1959[1] about representing a given context-free language in terms of two simpler languages.
The theorem Proofs of this theorem are found in several textbooks, e.g. Autebert, Berstel & Boasson (1997) or Davis, Sigal & Weyuker (1994).
A few notions from formal language theory are in order.
A context-free language is regular, if it can be described by a regular expression, or, equivalently, if it is accepted by a finite automaton.
A homomorphism is based on a function
which maps symbols from an alphabet
; If the domain of this function is extended to words over
contains the closing parenthesis symbols.
, the typed Dyck language
is context-free if and only if there exists We can interpret this as saying that any CFG language can be generated by first generating a typed Dyck language, filtering it by a regular grammar, and finally converting each bracket into a word in the CFG language.