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

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

Variantes et extensions

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

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 premiersUn mot de Dyck premier est un mot de Dyck non vide qui n'est pas produit de plusieurs mots de Dyck non vides, ou encore les langages des mots de Dyck bilatères ou bilatères premiersUn 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..

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

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.

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.

Notes et références

Bibliographie Sources

Extenions

Catégorie:Langage formel Chomsky Schützenberger Chomsky Schützenberger