Chomsky–Schützenberger enumeration theorem

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 Gruber, Lee & Shallit (2012): 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 ${\displaystyle G(x)}$ 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 ${\displaystyle S(x)}$, ${\displaystyle M(x)}$, and ${\displaystyle U(x)}$. The equation system can be resolved after S, resulting in a single algebraic equation:

${\displaystyle x(2x-1)S^{2}+(2x-1)S+1=0}$.

This quadratic equation has two solutions for S, one of which is the algebraic power series ${\displaystyle G(x)}$. By applying methods from complex analysis to this equation, the number ${\displaystyle a_{n}}$ of words of length n generated by G can be estimated, as n grows large. In this case, one obtains ${\displaystyle a_{n}\in O(2+\epsilon )^{n}}$ but ${\displaystyle a_{n}\notin O(2-\epsilon )^{n}}$ for each ${\displaystyle \epsilon >0}$. See (Gruber, Lee & Shallit 2012) for a detailed exposition.

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 ${\displaystyle L_{G}}$ over the alphabet ${\displaystyle \{a,b\}}$ consists of the words ${\displaystyle a^{n_{1}}ba^{n_{2}}b\cdots a^{n_{p}}b}$ with ${\displaystyle p\geq 1}$, ${\displaystyle n_{i}>0}$ for ${\displaystyle i\in \{1,2,\ldots ,p\}}$, and ${\displaystyle n_{j}\neq j}$ for some ${\displaystyle j\in \{1,2,\ldots ,p\}}$.

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