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

En informatique théorique, en mathématiques discrètes et en combinatoire, le théorème de Chomsky-Schützenberger est un énoncé sur le nombre de mots de longueur donnée dans un langage engendré par une grammaire algébrique inambiguë. Le théorème montre un lien entre la théorie des langages formels et l'algèbre. Il est nommé d'après Noam Chomsky et Marcel-Paul Schützenberger.

Énoncé

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

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

$f=f(x)=\sum _{k=0}^{\mathrm{\infty }}{a}_k{x}^k=a_0+a_1{x}^1+a_2{x}^2+a_3{x}^3+\cdots$

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

$f(x)\cdot g(x)=\sum _{k=0}^{\mathrm{\infty }}\left(\sum _{i=0}^k{a}_i{b}_{k-i}\right)x^k.$

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

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

Modèle:Théorème La série $f_L(x)$ est la série génératrice du nombre de mots du langage $L$. Des preuves de ce théorème sont données dans Modèle:Harvsp et Modèle:Harvsp.

Un exemple

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

$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 $y=f(x)$ du nombre de mots de Lukasiewicz vérifie l'équation

$y=x{y}^2+x$

Les coefficients $a_n$ sont les nombres de Catalan.

Une application

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 $f_L(x)$ d'un langage algébrique $L$ est transcendante, alors le langage $L$ est inhéremment ambigu.

On prouve ainsi que le langage de Goldstine $G$ est inhéremment ambiguModèle:,. On considère pour cela le complémentaire de ce langage ; il est formé des mots qui se terminent par la lettre $a$, et par les mots de l'ensemble

$F=\{\epsilon ,ab,ab{a}^{2}b,ab{a}^{2}b{a}^{3}b,\dots \}.$

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

$f_F(x)=1+x^2+x^5+x^9+\cdots =\sum _{n\ge 1}{x}^{n(n+1)/2-1}.$

Par conséquent,

$f_G(x)=\frac{1-x}{1-2x}-f_F(x).$

Comme $f_G(x)$ est transcendante si et seulement si $f_F(x)$ l'est, il suffit de considérer la dernière. Or, la série

$f_F(x)/x=\sum _{n\ge 1}{x}^{n(n+1)/2}$

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

Bibliographie

• Modèle:Chapitre
• Modèle:Ouvrage
• Modèle:Article
• Modèle:Article