Chomsky–Schützenberger theorem

In formal language theory, the Chomsky–Schützenberger theorem 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. It is named after Noam Chomsky and Marcel-Paul Schützenberger.

Statement of the theorem

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

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.$

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).

References

• Chomsky, Noam & Schützenberger, Marcel-Paul: "The Algebraic Theory of Context-Free Languages," in Computer Programming and Formal Systems, P. Braffort and D. Hirschberg (eds.), North Holland, pp. 118–161, 1963. Available online.
• Kuich, Werner & Salomaa, Arto: Semirings, Automata, Languages. Springer, 1985.
• Panholzer, Alois: "Gröbner Bases and the Defining Polynomial of a Context-free Grammar Generating Function." Journal of Automata, Languages and Combinatorics 10:79–97, 2005.