## You are here

HomeChomsky-Sch\"utzenberger theorem

## Primary tabs

# 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).

## Mathematics Subject Classification

68Q42*no label found*68Q45

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections