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. The theorem provides an unexpected link between the theory of formal languages and abstract algebra. It is named after Noam Chomsky and Marcel-Paul Schützenberger.

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

A power series over Failed to parse (Missing texvc executable; please see math/README to configure.): \mathbb{N}

with coefficients Failed to parse (Missing texvc executable; please see math/README to configure.): a_k

. The multiplication of two formal power series Failed to parse (Missing texvc executable; please see math/README to configure.): f

In particular, we write Failed to parse (Missing texvc executable; please see math/README to configure.): f^2 = f(x)\cdot f(x) , Failed to parse (Missing texvc executable; please see math/README to configure.): f^3 = f(x)\cdot f(x)\cdot f(x) , and so on. In analogy to algebraic numbers, a power series Failed to parse (Missing texvc executable; please see math/README to configure.): f(x)

Schützenberger may refer to these people:

Avram Noam Chomsky (/ˈnoʊm ˈtʃɒmski/; born December 7, 1928) is an American linguist, philosopher,cognitive scientist, historian, and activist. He is an Institute Professor and Professor (Emeritus) 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 a major figure of analytic philosophy. His work has influenced fields such as computer science, mathematics, and psychology.

Ideologically identifying with anarcho-syndicalism and libertarian socialism, Chomsky is known for his critiques of U.S. foreign policy and contemporary capitalism, and he has been described as a prominent cultural figure. His media criticism has included Manufacturing Consent: The Political Economy of the Mass Media (1988), co-written with Edward S. Herman, an analysis articulating the propaganda model theory for examining the media.

According to the Arts and Humanities Citation Index in 1992, Chomsky was cited as a source more often than any other living scholar from 1980 to 1992, and was the eighth most cited source overall. Chomsky is the author of over 100 books. He is credited as the creator or co-creator of the Chomsky hierarchy, the universal grammar theory, and the Chomsky–Schützenberger theorem.