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

Ambiguous grammar

In computer science, a context-free grammar is said to be an ambiguous grammar if there exists a string that can be generated by the grammar in more than one way...

. The theorem provides an unexpected link between the theory of formal languages and abstract algebra

Abstract algebra

Abstract algebra is the subject area of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras...

. It is named after Noam Chomsky

Noam Chomsky

Avram Noam Chomsky is an American linguist, philosopher, cognitive scientist, and activist. He is an Institute Professor and Professor in the Department of Linguistics & Philosophy at MIT, where he has worked for over 50 years. Chomsky has been described as the "father of modern linguistics" and...

 and Marcel-Paul Schützenberger

Marcel-Paul Schützenberger

Marcel-Paul "Marco" Schützenberger was a French mathematician and Doctor of Medicine. His work had impact across the fields of formal language, combinatorics, and information theory...

.

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

Convolution

In mathematics and, in particular, functional analysis, convolution is a mathematical operation on two functions f and g, producing a third function that is typically viewed as a modified version of one of the original functions. Convolution is similar to cross-correlation...

 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

Rational number

In mathematics, a rational number is any number that can be expressed as the quotient or fraction a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer is a rational number...

 coefficients such that


Having established the necessary notions, the theorem is stated as follows.

Chomsky–Schützenberger theorem. If is a context-free language

Context-free language

In formal language theory, a context-free language is a language generated by some context-free grammar. The set of all context-free languages is identical to the set of languages accepted by pushdown automata.-Examples:...

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