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 $h$ which maps symbols from an alphabet $\Gamma$ to words over another alphabet $\Sigma$ ; If the domain of this function is extended to words over $\Gamma$ in the natural way, by letting $h(xy)=h(x)h(y)$ for all words $x$ and $y$ , this yields a homomorphism $h:\Gamma ^{*}\to \Sigma ^{*}$ . A matched alphabet $T\cup \overline T$ is an alphabet with two equal-sized sets; it is convenient to think of it as a set of parentheses types, where $T$ contains the opening parenthesis symbols, whereas the symbols in $\overline T$ contains the closing parenthesis symbols. For a matched alphabet $T\cup \overline T$ , the Dyck language $D_{T}$ is given by

D_{T}=\{\,w\in (T\cup \overline T)^{*}\mid w{\text{ is a correctly nested sequence of parentheses}}\,\}

words that are well-nested parentheses over $T\cup \overline T$ .

Chomsky–Schützenberger theorem. A language L over the alphabet

\Sigma

is context-free if and only if there exists

a matched alphabet $T\cup \overline T$
a regular language $R$ over $T\cup \overline T$ ,
and a homomorphism $h:(T\cup \overline T)^{*}\to \Sigma ^{*}$

such that

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. External link in |title= (help)
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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.