Théorème de Chomsky-Schützenberger (combinatoire)

Pour énoncer le théorème, nous avons besoin de quelques notions d'algèbre.

Une série entière sur ${\displaystyle \mathbb {N} }$ est une série de la forme

${\displaystyle f=f(x)=\sum _{k=0}^{\infty }a_{k}x^{k}=a_{0}+a_{1}x^{1}+a_{2}x^{2}+a_{3}x^{3}+\cdots }$

à coefficients ${\displaystyle a_{k}}$ dans ${\displaystyle \mathbb {N} }$. La multiplication de deux séries entières ${\displaystyle f}$ et ${\displaystyle g}$ est définie, de manière habituelle, comme la convolution des suites ${\displaystyle a_{n}}$ et ${\displaystyle b_{n}}$ :

${\displaystyle f(x)\cdot g(x)=\sum _{k=0}^{\infty }{\Bigl (}\sum _{i=0}^{k}a_{i}b_{k-i}{\Bigr )}x^{k}.}$

En particulier, on écrit ${\displaystyle f^{2}=f(x)\cdot f(x)}$, ${\displaystyle f^{3}=f(x)\cdot f(x)\cdot f(x)}$, etc. En analogie avec les nombres algébriques, une série entière ${\displaystyle f(x)}$ est dite algébrique sur ${\displaystyle \mathbb {Q} (x)}$ s'il existe des polynômes ${\displaystyle p_{0}(x)}$, ${\displaystyle p_{1}(x)}$, ${\displaystyle p_{2}(x)}$, …, ${\displaystyle p_{n}(x)}$, à coefficients rationnels, tels que

${\displaystyle p_{0}(x)+p_{1}(x)\cdot f+p_{2}(x)\cdot f^{2}+\cdots +p_{n}(x)\cdot f^{n}=0.}$

Le théorème s'énonce comme suit.

La série ${\displaystyle f_{L}(x)}$ est la série génératrice du nombre de mots du langage ${\displaystyle L}$. Des preuves de ce théorème sont données dans Kuich & Salomaa (1985) et Panholzer (2005).

Le langage de Lukasiewicz est le langage engendré par la grammaire algébrique inambiguë

${\displaystyle S\to aSS|b}$

Un mot du langage code un arbre binaire, le codage étant obtenu par un parcours préfixe de l'arbre. La série génératrice ${\displaystyle y=f(x)}$ du nombre de mots de Lukasiewicz vérifie l'équation

${\displaystyle y=xy^{2}+x}$

Les coefficients ${\displaystyle a_{n}}$ sont les nombres de Catalan.