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
editIn 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.
- Chomsky–Schützenberger theorem. If is a context-free language admitting an unambiguous context-free grammar, and is the number of words of length in , then is a power series over that is algebraic over .
Proofs of this theorem are given by Kuich & Salomaa (1985), and by Panholzer (2005).
Usage
editAsymptotic estimates
editThe 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 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 , , 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 .[1]
The following example is from Bassino & Nicaud (2011): which simplifies to
Inherent ambiguity
editIn 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.[2] 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.[3]
Notes
edit- ^ See Gruber, Lee & Shallit (2012) for a detailed exposition.
- ^ Berstel & Boasson (1990).
- ^ See Berstel & Boasson (1990) for detailed account.
References
edit- Bassino, Frederique; Nicaud, Cyril (December 16, 2011). "Philippe Flajolet & Analytic Combinatorics: Inherent Ambiguity of Context-Free Languages" (PDF). inria.fr. Retrieved 5 April 2023.
- Berstel, Jean; Boasson, Luc (1990). "Context-free languages" (PDF). In van Leeuwen, Jan (ed.). Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics. Elsevier and MIT press. pp. 59–102. ISBN 0-444-88074-7.
- Chomsky, Noam; Schützenberger, Marcel-Paul (1963). "The Algebraic Theory of Context-Free Languages" (PDF). 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.
- Gruber, Hermann; Lee, Jonathan; Shallit, Jeffrey (2012). "Enumerating regular expressions and their languages". arXiv:1204.4982 [cs.FL].
- 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.