Chomsky–Schützenberger theorem

From Wikipedia, the free encyclopedia

In formal language theory, the Chomsky–Schützenberger theorem is either of two different theorems derived by Noam Chomsky and Marcel-Paul Schützenberger.

One of the two theorems is a statement about the number of words of a given length generated by an unambiguous context-free grammar. The theorem provides an unexpected link between the theory of formal languages and abstract algebra.

The other theorem, which bears the same name (Hotz & Kretschmer 1989), is a statement 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.

Statement of the theorem about counting words

In order to state the theorem, a few notions from algebra and formal language theory are needed.

A power series over ${\mathbb {N}}$ is an infinite series of the form

$f=f(x)=\sum _{{k=0}}^{\infty }a_{k}x^{k}=a_{0}+a_{1}x^{1}+a_{2}x^{2}+a_{3}x^{3}+\cdots$

with coefficients $a_{k}$ in ${\mathbb {N}}$ . The multiplication of two formal power series $f$ and $g$ is defined in the expected way as the convolution of the sequences $a_{n}$ and $b_{n}$ :

$f(x)\cdot g(x)=\sum _{{k=0}}^{\infty }\left(\sum _{{i=0}}^{k}a_{i}b_{{k-i}}\right)x^{k}.$

In particular, we write $f^{2}=f(x)\cdot f(x)$ , $f^{3}=f(x)\cdot f(x)\cdot f(x)$ , and so on. In analogy to algebraic numbers, a power series $f(x)$ is called algebraic over ${\mathbb {Q}}(x)$ , if there exists a finite set of polynomials $p_{0}(x),p_{1}(x),p_{2}(x),\ldots ,p_{n}(x)$ each with rational coefficients such that

$p_{0}(x)+p_{1}(x)\cdot f+p_{2}(x)\cdot f^{2}+\cdots +p_{n}(x)\cdot f^{n}=0.$

A context-free grammar is said to be unambiguous if every string generated by the grammar admits a unique parse tree, or, equivalently, only one leftmost derivation. Having established the necessary notions, the theorem is stated as follows.

Chomsky–Schützenberger theorem. If $L$ is a context-free language admitting an unambiguous context-free grammar, and $a_{k}:=|L\ \cap \Sigma ^{k}|$ is the number of words of length $k$ in $L$ , then $\sum _{{k=0}}^{\infty }a_{k}x^{k}$ is a power series over ${\mathbb {N}}$ that is algebraic over ${\mathbb {Q}}(x)$ .

Proofs of this theorem are given by Kuich & Salomaa (1985), and by Panholzer (2005).

Statement of the theorem about representing context-free languages

Also for the other theorem bearing this name, 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 given by Hotz & Kretschmer (1989) and Autebert, Berstel & Boasson (1997).

Bibliography

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.

Chomsky, Noam; Schützenberger, Marcel-Paul (1963). "The Algebraic Theory of Context-Free Languages". In P. Braffort and D. Hirschberg, eds., Computer Programming and Formal Systems (pp. 118–161). Amsterdam: North-Holland.

Flajolet, Philippe; Sedgewick, Robert (2009). Analytic Combinatorics. Cambridge: Cambridge University Press. ISBN 978-0-521-89806-5.

Hotz, G.; Kretschmer, T. (1989). "The power of the Greibach normal form". Elektronische Informationsverarbeitung und Kybernetik 25 (10): 507–512.

Kuich, Werner; Salomaa, Arto (1985). Semirings, Automata, Languages. Berlin: Springer-Verlag. ISBN 978-3-642-69961-0.

Panholzer, Alois (2005). "Gröbner Bases and the Defining Polynomial of a Context-free Grammar Generating Function". Journal of Automata, Languages and Combinatorics 10: 79–97.

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.