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

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

$L=h(D\cap K)$.

Ce théorème est prouvé dans plusieurs manuels, par exemple dans Automata and Computability 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

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

$L=h(g^{-1}(D_{2}^{*})\cap K)$,

où $D_{2}^{*}$ est le langage de Dyck sur deux paires de parenthèses, $K$ est un langage rationnel et $h,g$ sont des morphismes.

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:

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

$L=h(D\cap K)$,

où $D$ est un langage de Dyck , $K$ est un langage rationnel et $h$ 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 $L$ algébrique qui ne contient que des mots de longueur paire s'écrit sous la forme

$L=h(D\cap K)$,

où $D$ est un langage de Dyck, $K$ est un langage rationnel et $h$ 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 $L$ algébrique s'écrit sous la forme

$L=h(M\cap K)$,

où $M$ est un langage de Motzkin, $K$ est un langage rationnel et $h$ est un morphisme lettre-à-lettre, c'est-à-dire préservant la longueur.

Bibliographie

Sources

• (en) Noam Chomsky et Marcel-Paul Schützenberger, « The Algebraic Theory of Context-Free Languages », dans Paul Braffort et D. Hirschberg (éditeurs), Computer Programming and Formal Systems, North Holland, 1963 (lire en ligne), p. 118-161

• (en) Dexter Kozen, Automata and Computability, Springer Verlag, coll. « Undergraduate Texts in Computer Science », 1997, 400 p. (ISBN 978-0-387-94907-9, présentation en ligne)

Extenions

• Stefano Crespi Reghizzi, Antonio Restivo et Pierluigi San Pietro, « From words to pictures: Row-column combinations and Chomsky-Schützenberger theorem », Theoretical Computer Science, vol. 1002,‎ juin 2024, p. 114598 (DOI 10.1016/j.tcs.2024.114598, lire en ligne, consulté le 29 mai 2024)