Chomsky–Schützenberger representation theorem

Remarks

The direction "if" holds because $D_n$ is context-free and the context-free languages are closed under intersection with regular languages and under homomorphisms. For "only if", take a grammar for $L$ in Chomsky normal form and give each rule its own brackets. A derivation is then encoded as a balanced bracket string. The regular language $R$ checks the local consistency of the encoding, and $h$ erases the brackets and keeps the letters. Example: $\set{a^m b^m : m \ge 0} = h(D_1 \cap R)$ with $R = [_1^* \, ]_1^*$, $h([_1) = a$ and $h(]_1) = b$. Indeed $D_1 \cap R = \set{[_1^m \, ]_1^m : m \ge 0}$.

Going deeper

For a student

The theorem gives an algebraic description of the context-free languages, without grammars or automata. It is often used with $D_2$ alone, since each $D_n$ is the inverse image of $D_2$ under a suitable homomorphism, and the class is closed under inverse homomorphisms. In the language of abstract families of languages, it says that the context-free languages form the smallest full trio containing $D_2$.