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

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Ne pas confondre avec le théorème de Chomsky-Schützenberger sur la représentation des langages algébriques.

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 qu'un lien existe 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é[modifier | modifier le code]

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

Une série entière sur ℕ est une série de la forme

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 a_k dans ℕ. 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}^\infty \Bigl(\sum_{i=0}^k a_i b_{k-i}\Bigr) x^k.

En particulier, on écrit \scriptstyle f^2 = f(x)\cdot f(x), \scriptstyle 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 ℚ(x) s'il existe des polynômes \scriptstyle p_0(x), p_1(x), p_2(x), \ldots , 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.

Théorème de Chomsky-Schützenberger —  Soit L un langage algébrique sur un alphabet A admettant une grammaire algébrique inambiguë, et soit \scriptstyle a_k := | L\cap A^k | le nombre de mots de longueur k dans L. La série

f_L(x)=\sum_{k = 0}^\infty a_k x^k

est une série entière sur ℕ qui est algébrique sur ℚ(x).

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 Kuich & Salomaa (1985) et Panholzer (2005).

Un exemple[modifier | modifier le code]

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

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 grammaire est inambiguë. La série génératrice y=f(x) du nombre de mots de Lukasiewicz vérifie l'équation

y=xy^2+x

Les coefficients a_n sont les nombres de Catalan.

Une application[modifier | modifier le code]

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 ambigu[1]. 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=\{\varepsilon, ab, aba^b,aba^2ba^3b,\ldots\}.

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\ge1}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\ge1}x^{n(n+1)/2}

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

Notes et références[modifier | modifier le code]

  1. L'exposé suit Flajolet (1987).

Bibliographie[modifier | modifier le code]

  • (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 (en), 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