Chomsky–Schützenberger Theorem

languages

Definition

Chomsky–Schützenberger Theorem

Let Let $D_n$ over ${\Gamma }_n$ be a Dyck language.

A language $L$ over $\Sigma$ is context-free iff there exists some $n\ge 0$ and a homomorphism $h:{\Gamma }_n^{\ast }\to {\Sigma }^{\ast }$ such that:

$$L=h(D_n\cap R)$$

where $R$ denotes a regular language over ${\Gamma }_n$.

Example

Example 1

$$L=\{a^n{b}^n\mid n\ge 0\}=h(D_1\cap \{({\}}^{\ast }\{){\}}^{\ast })$$

where $h:\{(,){\}}^{\ast }\to \{a,b{\}}^{\ast }$ with $h(()=a$ and $h())=b$.

Therefore, $L$ is context-free.

Example 2