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

En informatique théorique, et notamment en théorie des langages formels, le théorème de Chomsky-Schützenberger est un théorème de représentation. Il affirme que tout langage algébrique peut s'exprimer, au moyen d'une certaine construction, à partir d'un langage de Dyck. En ce sens, le théorème affirme que les langages de Dyck sont des langages algébriques « typiques ». Ce théorème est nommé ainsi d'après Noam Chomsky et Marcel-Paul Schützenberger. Il figure dans leur article commun de 1963[1].

Énoncé du théorème modifier

Dans l’énoncé suivant, on utilise le terme morphisme alphabétique. Un morphisme   entre monoïdes libres est dit alphabétique si l'image d'une lettre de   est une lettre de   ou le mot vide. C'est, de manière équivalente, un morphisme décroissant, c'est-à-dire tel que la longueur de l'image   d'un mot   est toujours inférieure ou égale à la longueur du mot  .

Théorème de Chomsky-Schützenberger — Un langage   est algébrique si et seulement s'il existe un langage de Dyck  , un langage rationnel   et un morphisme alphabétique   tels que

 .

Ce théorème est prouvé dans plusieurs manuels, par exemple dans Automata and Computability de Dexter Kozen[2].

Variantes et extensions modifier

Dans l'énoncé ci-dessus, le langage rationnel   et le langage de Dyck   dépendent bien entendu du langage   que l'on veut représenter. Une variante consiste à choisir, moyennant une construction un peu plus compliquée, un langage de Dyck unique, à savoir le langage de Dyck sur deux paires de parenthèses. On a alors

Théorème — Un langage   est algébrique si et seulement s'il s'écrit sous la forme

 ,

  est le langage de Dyck sur deux paires de parenthèses,   est un langage rationnel et   sont des morphismes.

De manière équivalente, cet énoncé signifie que tout langage algébrique est image de   par une transduction rationnelle, ou encore que le langage   est un générateur du cône rationnel des langages algébriques.

D'autres langages peuvent jouer le rôle de   dans l'énoncé ci-dessus, comme le langage des mots de Dyck premiers[3], ou encore les langages des mots de Dyck bilatères ou bilatères premiers[4].

Au lieu de fixer le nombre de paires de parenthèses à deux, tout nombre supérieur ou égal à deux convient. En revanche, le résultat cesse d'être vrai pour les langages de Dyck sur une seule paire de parenthèses.

Une autre variante, ou plutôt une précision, concerne la nature de l'homomorphisme   du théorème. La question est de savoir si on peut supposer ce morphisme non effaçant. Une réponse négative vient vite à l'esprit : puisque le langage de Dyck ne contient pas de mot de longueur 1, on ne peut obtenir, dans le langage image, de mot de longueur 1. En fait, il apparaît que c'est la seule contrainte. Alexander Okhotin a prouvé l'énoncé suivant[5]:

Théorème — Tout langage   algébrique ne contenant pas de mot réduit à une lettre s'écrit sous la forme

 ,

  est un langage de Dyck ,   est un langage rationnel et   est un morphisme non effaçant.

La preuve utilise, entre autres, la forme normale de Greibach bilatère des grammaires algébriques. Deux énoncés complémentaires, du même article, méritent d'être mentionnés dans ce contexte.

Proposition — Tout langage   algébrique qui ne contient que des mots de longueur paire s'écrit sous la forme

 ,

  est un langage de Dyck,   est un langage rationnel et   est un morphisme lettre-à-lettre, c'est-à-dire préservant la longueur.

Enfin, on a un théorème semblable au théorème de Chomsky-Schützenberger en remplaçant le langage de Dyck par le langage de Motzkin, c'est-à-dire un langage obtenu à partir d'un langage de Dyck en insérant des lettres « neutres » en quantité quelconque.

Proposition — Tout langage   algébrique s'écrit sous la forme

 ,

  est un langage de Motzkin,   est un langage rationnel et   est un morphisme lettre-à-lettre, c'est-à-dire préservant la longueur.

Notes et références modifier

  1. Chomsky-Schützenberger (1963).
  2. Dexter Kozen, Automata and Computability (1997), p. 198-200.
  3. Un mot de Dyck premier est un mot de Dyck non vide qui n'est pas produit de plusieurs mots de Dyck non vides
  4. Un mot de Dyck bilatère premier est une mot de Dyck bilatère non vide qui n'est pas produit d'autres mots de Dyck bilatères premiers.
  5. Alexander Okhotin, « Non-erasing variants of the Chomsky-Schützenberger theorem », dans H.-C. Yen et O.H. Ibarra (éditeurs), Developments in Language Theory : DLT 2012, Springer-Verlag, coll. « Lecture Notes in Computer Science » (no 7410), , p. 121–129 .

Bibliographie modifier