Chomsky-Schützenberger Representation Theorem

Moritz Roos 📧

June 2, 2025

Abstract

The Chomksy-Schützenberger Representation Theorem says that any context-free language is the homomorphic image of the intersection of a regular language and a Dyck language.

License

BSD License

Topics

Related publications

  • Chomsky, N., & Schützenberger, M. P. (1959). The Algebraic Theory of Context-Free Languages. Computer Programming and Formal Systems, 118–161. https://doi.org/10.1016/s0049-237x(09)70104-1
  • https://en.wikipedia.org/wiki/Chomsky%E2%80%93Sch%C3%BCtzenberger_representation_theorem

Session Chomsky_Schuetzenberger

Depends on

Cite

× 
@article{Chomsky_Schuetzenberger-AFP,
  author  = {Moritz Roos},
  title   = {Chomsky-Schützenberger Representation Theorem},
  journal = {Archive of Formal Proofs},
  month   = {June},
  year    = {2025},
  note    = {\url{https://isa-afp.org/entries/Chomsky_Schuetzenberger.html},
             Formal proof development},
  ISSN    = {2150-914x},
}
Download