Chomsky–Schützenberger representation theorem
In formal language theory, the Chomsky–Schützenberger representation theorem is a theorem derived by Noam Chomsky and Marcel-Paul Schützenberger about representing a given context-free language in terms of two simpler languages. These two simpler languages, namely a regular language and a Dyck language, are combined by means of an intersection and a homomorphism.
A few notions from formal language theory are in order. A context-free language is regular, if it can be described by a regular expression, or, equivalently, if it is accepted by a finite automaton. A homomorphism is based on a function which maps symbols from an alphabet to words over another alphabet ; If the domain of this function is extended to words over in the natural way, by letting for all words and , this yields a homomorphism . A matched alphabet is an alphabet with two equal-sized sets; it is convenient to think of it as a set of parentheses types, where contains the opening parenthesis symbols, whereas the symbols in contains the closing parenthesis symbols. For a matched alphabet , the Dyck language is given by
Chomsky–Schützenberger theorem. A language L over the alphabet is context-free if and only if there exists
- a matched alphabet
- a regular language over ,
- and a homomorphism
- such that .
Proofs of this theorem are found in several textbooks, e.g. Autebert, Berstel & Boasson (1997) or Davis, Sigal & Weyuker (1994).
References
- Autebert, Jean-Michel; Berstel, Jean; Boasson, Luc (1997). "Context-Free Languages and Push-Down Automata" (PDF). In G. Rozenberg and A. Salomaa, eds., Handbook of Formal Languages, Vol. 1: Word, Language, Grammar (pp. 111–174). Berlin: Springer-Verlag. ISBN 3-540-60420-0.
- Davis, Martin D.; Sigal, Ron; Weyuker, Elaine J. (1994). Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science (2nd ed.). Elsevier Science. p. 306. ISBN 0-12-206382-1.
- v
- t
- e
- Bibliography
- Chomsky hierarchy
- "Colorless green ideas sleep furiously"
- Honorary degrees
- Political positions
bibliography
works about
- Chomsky
- Chomsky's Universal Grammar: An Introduction
- Decoding Chomsky
- Noam Chomsky: A Life of Dissent
- The Anti-Chomsky Reader
- The Cambridge Companion to Chomsky
- The Kingdom of Speech
- Manufacturing Consent: Noam Chomsky and the Media (1992)
- Last Party 2000 (2001)
- Power and Terror: Noam Chomsky in Our Times (2002)
- Distorted Morality – America's War on Terror? (2003)
- Noam Chomsky: Rebel Without a Pause (2003) (TV)
- Peace, Propaganda & the Promised Land (2004)
- Is the Man Who Is Tall Happy? (2013)
- William Chomsky (father)
- Carol Chomsky (deceased wife)
- Valeria Wasserman (wife)
- Aviva Chomsky (daughter)