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.

Par contraposition, le théorème de Chomsky-Schützenberger donne un moyen de prouver qu'un langage est inhéremment ambigu, autre que le lemme d'Ogden :

Si la série génératrice ${\displaystyle f_{L}(x)}$ d'un langage algébrique ${\displaystyle L}$ est transcendante, alors le langage ${\displaystyle L}$ est inhéremment ambigu.

On prouve ainsi que le langage de Goldstine ${\displaystyle G}$ est inhéremment ambigu[1] - [2]. On considère pour cela le complémentaire de ce langage ; il est formé des mots qui se terminent par la lettre ${\displaystyle a}$, et par les mots de l'ensemble

${\displaystyle F=\{\varepsilon ,ab,aba^{2}b,aba^{2}ba^{3}b,\ldots \}.}$

La série génératrice des mots se terminant par la lettre ${\displaystyle a}$ est ${\displaystyle x/(1-2x)}$. La série génératrice de l'ensemble ${\displaystyle F}$ est

${\displaystyle f_{F}(x)=1+x^{2}+x^{5}+x^{9}+\cdots =\sum _{n\geq 1}x^{n(n+1)/2-1}.}$

Par conséquent,

${\displaystyle f_{G}(x)={\frac {1-x}{1-2x}}-f_{F}(x).}$

Comme ${\displaystyle f_{G}(x)}$ est transcendante si et seulement si ${\displaystyle f_{F}(x)}$ l'est, il suffit de considérer la dernière. Or, la série

${\displaystyle f_{F}(x)/x=\sum _{n\geq 1}x^{n(n+1)/2}}$

est transcendante, car c'est une série lacunaire.

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Chomsky–Schützenberger theorem » (voir la liste des auteurs).

• (en) Noam Chomsky et Marcel-Paul Schützenberger, « The algebraic theory of context-free languages », dans P. Braffort et D. Hirschberg (éditeurs), Computer Programming and Formal Systems, North Holland, 1963, p. 118-161
• (en) Werner Kuich et Arto Salomaa, Semirings, Automata, Languages, Springer-Verlag, 1985
• (en) Alois Panholzer, « Gröbner bases and the defining polynomial of a context-free grammar generating function », Journal of Automata, Languages and Combinatorics, vol. 10,‎ 2005, p. 79-97
• (en) Philippe Flajolet, « Analytic models and ambiguity of context-free languages », Theoret. Comput. Sci., vol. 49,‎ 1987, p. 283-309