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.

Title	Chomsky-Schützenberger theorem
Canonical name	ChomskySchutzenbergerTheorem
Date of creation	2013-03-22 18:55:40
Last modified on	2013-03-22 18:55:40
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	5
Author	CWoo (3771)
Entry type	Theorem
Classification	msc 68Q42
Classification	msc 68Q45