In order to state the theorem, a few notions from algebra and formal language theory are needed. Let denote the set of nonnegative integers. A power series over is an infinite series of the form with coefficients in. The multiplication of two formal power series and is defined in the expected way as the convolution of the sequences and : In particular, we write,, and so on. In analogy to algebraic numbers, a power series is called algebraic over, if there exists a finite set of polynomials each with rational coefficients such that 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. Proofs of this theorem are given by, and by.
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 : the unambiguous context-free grammar G over the alphabet has start symbolS and the following rules To obtain an algebraic representation of the power series 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: In this system of equations, S, M, and U are functions of x, so one could also write,, and. The equation system can be resolved after S, resulting in a single algebraic equation: This quadratic equation has two solutions for S, one of which is the algebraic power series. By applying methods from complex analysis to this equation, the number of words of length n generated by G can be estimated, as n grows large. In this case, one obtains but for each. See for a detailed exposition.
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 over the alphabet consists of the words with, for, and for some. It is comparably easy to show that the language is context-free. The harder part is to show that there does not exist an unambiguous grammar that generates. This can be proved as follows: If denotes the number of words of length in, then for the associated power series holds Using methods from complex analysis, one can prove that this function is not algebraic over. By the Chomsky-Schützenberger theorem, one can conclude that does not admit an unambiguous context-free grammar. See for detailed account.
