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 Σ is context-free iff for some n0, there there is a homomorphismMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath h:Σn*Σ* such that

L=h(𝐏𝐚𝐫𝐞𝐧𝒏R),

where Paren𝐧 is the parenthesis language over Σn, and R is a regular language (over Σ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 intersectionMathworldPlanetmathPlanetmath 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