Chomsky–Schützenberger enumeration theorem

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.

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

A power series over ${\displaystyle \mathbb {N} }$ is an infinite series of the form

with coefficients ${\displaystyle a_{k}}$ in ${\displaystyle \mathbb {N} }$. The multiplication of two formal power series ${\displaystyle f}$ and ${\displaystyle g}$ is defined in the expected way as the convolution of the sequences ${\displaystyle a_{n}}$ and ${\displaystyle b_{n}}$:

...
Wikipedia