# 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 $\Sigma$ is context-free iff for some $n\geq 0$, there there is a homomorphism $h:\Sigma_{n}^{*}\to\Sigma^{*}$ such that

 $L=h(\boldsymbol{\operatorname{Paren}_{n}}\cap R),$

where $\boldsymbol{\operatorname{Paren}_{n}}$ is the parenthesis language over $\Sigma_{n}$, and $R$ is a regular language (over $\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.

## References

• 1 N. Chomsky, M.P. Schützenberger, The Algebraic Theory of Context-Free Languages, Computer Programming and Formal Systems, North-Holland, Amsterdam (1963).
• 2 D. C. Kozen, Automata and Computability, Springer, New York (1997).
Title Chomsky-Schützenberger theorem ChomskySchutzenbergerTheorem 2013-03-22 18:55:40 2013-03-22 18:55:40 CWoo (3771) CWoo (3771) 5 CWoo (3771) Theorem msc 68Q42 msc 68Q45