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 ${\displaystyle h}$ which maps symbols from an alphabet ${\displaystyle \Gamma }$ to words over another alphabet ${\displaystyle \Sigma }$; If the domain of this function is extended to words over ${\displaystyle \Gamma }$ in the natural way, by letting ${\displaystyle h(xy)=h(x)h(y)}$ for all words ${\displaystyle x}$ and ${\displaystyle y}$, this yields a homomorphism ${\displaystyle h:\Gamma ^{*}\to \Sigma ^{*}}$. A matched alphabet ${\displaystyle T\cup {\overline {T}}}$ is an alphabet with two equal-sized sets; it is convenient to think of it as a set of parentheses types, where ${\displaystyle T}$ contains the opening parenthesis symbols, whereas the symbols in ${\displaystyle {\overline {T}}}$ contains the closing parenthesis symbols. For a matched alphabet ${\displaystyle T\cup {\overline {T}}}$, the Dyck language ${\displaystyle D_{T}}$ is given by

...
Wikipedia