Chomsky–Schützenberger enumeration theorem

In formal language theory, the Chomsky–Schützenberger enumeration theorem is a theorem derived by Noam Chomsky and Marcel-Paul Schützenberger 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.

Statement

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

Let $\mathbb{N}$ denote the set of nonnegative integers. A power series over $\mathbb{N}$ is an infinite series of the form

$f=f(x)=\sum _{k=0}^{\mathrm{\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}^{\mathrm{\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),\dots ,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 {\mathrm{\Sigma }}^k|$ is the number of words of length $k$ in $L$, then $G(x)=\sum _{k=0}^{\mathrm{\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 Template:Harvtxt, and by Template:Harvtxt.

Usage

Asymptotic estimates

The theorem can be used in analytic combinatorics to estimate the number of words of length n generated by a given unambiguous context-free grammar, as n grows large. The following example is given by Template:Harvtxt: the unambiguous context-free grammar G over the alphabet {0,1} has start symbol S and the following rules

S → M | U

M → 0M1M | ε

U → 0S | 0M1U.

To obtain an algebraic representation of the power series Template:Tmath associated with a given context-free grammar G, one transforms the grammar into a system of equations. This is achieved by replacing each occurrence of a terminal symbol by x, each occurrence of ε by the integer '1', each occurrence of '→' by '=', and each occurrence of '|' by '+', respectively. The operation of concatenation at the right-hand-side of each rule corresponds to the multiplication operation in the equations thus obtained. This yields the following system of equations:

S = M + U

M = M²x² + 1

U = Sx + MUx²

In this system of equations, S, M, and U are functions of x, so one could also write Template:Tmath, Template:Tmath, and Template:Tmath. The equation system can be resolved after S, resulting in a single algebraic equation:

Template:Tmath.

This quadratic equation has two solutions for S, one of which is the algebraic power series Template:Tmath. By applying methods from complex analysis to this equation, the number $a_n$ of words of length n generated by G can be estimated, as n grows large. In this case, one obtains $a_n\in O(2+ϵ{)}^n$ but $a_n\notin O(2-ϵ{)}^n$ for each $ϵ>0$.

The following example is from Template:Harvtxt:$$\{\begin{array}{c}S\to XY\\ T\to aT|TbT|YcY\\ Y\to YaY|cY|abTaYYa|X\\ X\to a|b|c\end{array}\Rightarrow \{\begin{array}{c}s(z)=x(z)y(z)\\ t(z)=zt(z)+zt(z{)}^2+zy(z{)}^2\\ y(z)=zy(z{)}^2+zy(z)+z^{4}t(z)y(z{)}^2+x(z)\\ x(z)=3z\end{array}$$which simplifies to$$s(z{)}^8-27(z^3-z^2)s(z{)}^5+\dots +59049z^{10}=0$$

Inherent ambiguity

In classical formal language theory, the theorem can be used to prove that certain context-free languages are inherently ambiguous. For example, the Goldstine language $L_G$ over the alphabet $\{a,b\}$ consists of the words $a^{n_1}b{a}^{n_2}b\cdots a^{n_p}b$ with $p\ge 1$, $n_i>0$ for $i\in \{1,2,\dots ,p\}$, and $n_j\ne j$ for some $j\in \{1,2,\dots ,p\}$.

It is comparably easy to show that the language $L_G$ is context-free.Template:Sfnp The harder part is to show that there does not exist an unambiguous grammar that generates $L_G$. This can be proved as follows: If $g_k$ denotes the number of words of length $k$ in $L_G$, then for the associated power series holds $G(x)=\sum _{k=0}^{\mathrm{\infty }}{g}_k{x}^k=\frac{1-x}{1-2x}-\frac{1}{x}\sum _{k\ge 1}{x}^{k(k+1)/2-1}$. Using methods from complex analysis, one can prove that this function is not algebraic over $\mathbb{Q}(x)$. By the Chomsky-Schützenberger theorem, one can conclude that $L_G$ does not admit an unambiguous context-free grammar.

References

• Template:Cite web
• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Cite arXiv
• Template:Cite book
• Template:Cite journal