Chomsky–Schützenberger representation theorem

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 can be described by a regular expression, or, equivalently, if it is accepted by a finite automaton. A homomorphism is based on a function {displaystyle h} which maps symbols from an alphabet {displaystyle Gamma } to words over another alphabet {displaystyle Sigma } ; If the domain of this function is extended to words over {displaystyle Gamma } in the natural way, by letting {displaystyle h(xy)=h(x)h(y)} for all words {displaystyle x} and {displaystyle y} , this yields a homomorphism {displaystyle h:Gamma ^{*}to Sigma ^{*}} . A matched alphabet {displaystyle Tcup {overline {T}}} is an alphabet with two equal-sized sets; it is convenient to think of it as a set of parentheses types, where {displaystyle T} contains the opening parenthesis symbols, whereas the symbols in {displaystyle {overline {T}}} contains the closing parenthesis symbols. For a matched alphabet {displaystyle Tcup {overline {T}}} , the Dyck language {displaystyle D_{T}} is given by {displaystyle D_{T}={,win (Tcup {overline {T}})^{*}mid w{text{ is a correctly nested sequence of parentheses}},}.} Chomsky–Schützenberger theorem. A language L over the alphabet {displaystyle Sigma } is context-free if and only if there exists a matched alphabet {displaystyle Tcup {overline {T}}} a regular language {displaystyle R} over {displaystyle Tcup {overline {T}}} , and a homomorphism {displaystyle h:(Tcup {overline {T}})^{*}to Sigma ^{*}} such that {displaystyle L=h(D_{T}cap R)} .

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. hide vte Noam Chomsky BibliographyChomsky hierarchy"Colorless green ideas sleep furiously"Honorary degreesPolitical positions Select bibliography Linguistics Syntactic Structures (1957)Current Issues in Linguistic Theory (1964)Aspects of the Theory of Syntax (1965)Cartesian Linguistics (1966)Language and Mind (1966)The Sound Pattern of English (1968)"Remarks on Nominalization" (1970)"Conditions on Transformations" (1973)Reflections on Language (1975)The Logical Structure of Linguistic Theory (1975)Lectures on Government and Binding (1981)Knowledge of Language (1986)The Minimalist Program (1995)New Horizons in the Study of Language and Mind (2000) Politics "The Responsibility of Intellectuals" (1967)American Power and the New Mandarins (1969)Counter-Revolutionary Violence (1973), with Edward S. HermanThe Fateful Triangle (1983)Manufacturing Consent (1988), with Edward S. HermanNecessary Illusions (1989)Deterring Democracy (1991)Letters from Lexington (1993)The Prosperous Few and the Restless Many (1993)World Orders Old and New (1994)Objectivity and Liberal Scholarship (1997)Hegemony or Survival (2003)Failed States (2006)Requiem for the American Dream (2017) Collections Class Warfare (1996)Middle East Illusions (2003)Imperial Ambitions (2005)Interventions (2007)Gaza in Crisis (2010)9-11: Was There An Alternative? (2011)Making the Future (2012)Occupy (2012)On Palestine (2015), with Ilan Pappé Filmography 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) Family William Chomsky (father)Carol Chomsky (wife)Aviva Chomsky (daughter) Categories: Noam ChomskyFormal languagesTheorems in discrete mathematics