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

[math]\displaystyle{ D_T = \{\,w \in (T \cup \overline T)^* \mid w \text{ is a correctly nested sequence of parentheses} \,\}. }[/math]

Chomsky–Schützenberger theorem. A language L over the alphabet [math]\displaystyle{ \Sigma }[/math] is context-free if and only if there exists

• a matched alphabet [math]\displaystyle{ T \cup \overline T }[/math]
• a regular language [math]\displaystyle{ R }[/math] over [math]\displaystyle{ T \cup \overline T }[/math],
• and a homomorphism [math]\displaystyle{ h : (T \cup \overline T)^* \to \Sigma^* }[/math]

such that [math]\displaystyle{ L = h(D_T \cap R) }[/math].

Proofs of this theorem are found in several textbooks, e.g. (Autebert Berstel) or (Davis Sigal).

References

• Autebert, Jean-Michel; Berstel, Jean; Boasson, Luc (1997). "Context-Free Languages and Push-Down Automata". 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. http://www-igm.univ-mlv.fr/~berstel/Articles/1997CFLPDA.pdf. 
• 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.