# 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{\mathbf{P}\mathbf{a}\mathbf{r}\mathbf{e}\mathbf{n}}}_{\bm{n}}\cap R),$$ |

where ${\mathrm{Paren}}_{\mathbf{n}}$ 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.

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

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 |