Chomsky-Schützenberger theorem

An important characterization of context-free languages is captured in what is known as the Chomsky-Schützenberger theorem. It shows the intimate connection between context-free and parenthesis languages.

Theorem 1 (Chomsky-Schützenberger).

A langauge $L$ over an alphabet $\mathrm{\Sigma }$ is context-free iff for some $n\mathrm{\ge }\mathrm{0}$, there there is a homomorphism $h\mathrm{:}{\mathrm{\Sigma }}_n^{\mathrm{*}}\mathrm{\to }{\mathrm{\Sigma }}^{\mathrm{*}}$ such that

$$L=h({\mathrm{𝐏𝐚𝐫𝐞𝐧}}_{𝒏}\cap R),$$

where ${\mathrm{Paren}}_{𝐧}$ is the parenthesis language over ${\mathrm{\Sigma }}_n$, and $R$ is a regular language (over ${\mathrm{\Sigma }}_n$).

Note that the “if” part is the trivial consequence of the following facts: parenthesis languages are context-free; any homomorphic image of a context-free language is context-free; any intersection of a context-free language with a regular language is context-free.