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.

Énoncé du théorème

Dans l’énoncé suivant, on utilise le terme morphisme alphabétique. Un morphisme $h:A^{*}\to B^{*}$ entre monoïdes libres est dit alphabétique si l'image d'une lettre de $A$ est une lettre de $B$ ou le mot vide. C'est, de manière équivalente, un morphisme décroissant, c'est-à-dire tel que la longueur de l'image $h(w)$ d'un mot $w$ est toujours inférieure ou égale à la longueur du mot $w$.

Ce théorème est prouvé dans plusieurs manuels, par exemple dans Modèle:Langue de Dexter Kozen.

Variantes et extensions

Dans l'énoncé ci-dessus, le langage rationnel $K$ et le langage de Dyck $D$ dépendent bien entendu du langage $L$ 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

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

D'autres langages peuvent jouer le rôle de $D_2^{*}$ dans l'énoncé ci-dessus, comme le langage des mots de Dyck premiers, ou encore les langages des mots de Dyck bilatères ou bilatères premiers.

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 $h$ 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: Modèle:Théorème 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. Modèle:Théorème 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. Modèle:Théorème

Bibliographie

Sources

• Modèle:Chapitre

• Modèle:Ouvrage

Extenions

• Modèle:Article