Théorème de Myhill-Nerode

Étant donné un langage ${\displaystyle L}$ et deux mots ${\displaystyle x}$ et ${\displaystyle y}$, on dit qu'un mot ${\displaystyle z}$ sépare ${\displaystyle x}$ et ${\displaystyle y}$ si un et un seul des mots ${\displaystyle xz}$ et ${\displaystyle yz}$ est dans le langage ${\displaystyle L}$. Deux mots ${\displaystyle x}$ et ${\displaystyle y}$ sont inséparables (undistiguishable en anglais) s'il n'existe pas de mot ${\displaystyle z}$ qui les sépare.

On définit une relation ${\displaystyle R_{L}}$ sur les mots, appelée relation de Myhill-Nerode, par la règle : ${\displaystyle xR_{L}y}$ si et seulement si ${\displaystyle x}$ et ${\displaystyle y}$ sont inséparables. Il est facile de montrer que la relation ${\displaystyle R_{L}}$ est une relation d'équivalence sur les mots, et donc partitionne l'ensemble de tous les mots en classes d'équivalences. Le nombre de classes est appelé l'index de la relation. Il peut être fini ou infini.

Soit ${\displaystyle L}$ un langage rationnel. Il existe un automate fini déterministe complet qui reconnaît ${\displaystyle L}$. Pour chaque état ${\displaystyle q}$ de cet automate, soit ${\displaystyle P_{q}}$ l’ensemble des mots ${\displaystyle w}$ qui mènent de l'état initial à ${\displaystyle q}$. Si ${\displaystyle x}$ et ${\displaystyle y}$ sont deux mots de ${\displaystyle P_{q}}$, alors pour tout mot ${\displaystyle z}$, les mots ${\displaystyle xz}$ et ${\displaystyle yz}$ mènent au même état, qu'il soit acceptant ou non. Ainsi, aucun mot ${\displaystyle z}$ ne peut séparer ${\displaystyle x}$ et ${\displaystyle y}$, et ils sont donc inséparables. Ceci montre que l'ensemble ${\displaystyle P_{q}}$ est contenu dans une classe de l'équivalence ${\displaystyle R_{L}}$, et comme tout mot est dans un des ensembles ${\displaystyle P_{q}}$, l'index de la relation est inférieur ou égal au nombre d'états de l'automate, et donc est fini.

Réciproquement, supposons que la relation de Myhill-Nerode ${\displaystyle R_{L}}$ est d'index fini. Dans ce cas, on construit un automate fini reconnaissant ${\displaystyle L}$ comme suit. Les états sont les classes de l'équivalence ${\displaystyle R_{L}}$. L'état initial est la classe d'équivalence du mot vide, et la fonction de transition mène, pour un état ${\displaystyle p}$ et une lettre ${\displaystyle a}$, à l'état ${\displaystyle q}$ qui contient le mot ${\displaystyle xa}$, où ${\displaystyle x}$ est un mot quelconque de ${\displaystyle p}$. La définition de l'équivalence ${\displaystyle R_{L}}$ assure que la fonction de transition est bien définie : si ${\displaystyle xR_{L}y}$, alors ${\displaystyle xaR_{L}ya}$ pour toute lettre ${\displaystyle a}$, car si un mot ${\displaystyle z}$ était un séparateur de ${\displaystyle xa}$ et ${\displaystyle ya}$, alors ${\displaystyle az}$ séparerait ${\displaystyle x}$ et ${\displaystyle y}$. Un état de l'automate est final s'il contient un mot de ${\displaystyle L}$. Comme précédemment, la définition de la relation ${\displaystyle R_{L}}$ implique alors que tous les éléments de cette classe sont dans ${\displaystyle L}$, sinon le mot vide pourrait séparer des mots de cette classe.

Ainsi, l'existence d'un automate fini reconnaissant ${\displaystyle L}$ implique que la relation ${\displaystyle R_{L}}$ est d'index fini, et d'index au plus égal au nombre de d'états de l'automate, et la finitude de l'index de ${\displaystyle R_{L}}$ implique l'existence d'un automate ayant ce nombre d'états.

Étant donné un langage ${\displaystyle L}$ de ${\displaystyle A^{*}}$ et un mot ${\displaystyle x}$, le quotient gauche de ${\displaystyle L}$ par ${\displaystyle x}$, ou le résiduel de ${\displaystyle L}$ par ${\displaystyle x}$, est l'ensemble noté ${\displaystyle x^{-1}L}$ défini par

${\displaystyle x^{-1}L=\{z\in A^{*}\mid xz\in L\}}$ .

Avec cette notation, deux mots ${\displaystyle x}$ et ${\displaystyle y}$ sont inséparables si et seulement si ${\displaystyle x^{-1}L=y^{-1}L}$. Les classes de l'équivalence de Myhill-Nerode sont donc en bijection avec les résiduels de ${\displaystyle L}$. Il en résulte qu'un langage est rationnel si et seulement si l'ensemble de ses résiduels est fini. C'est sous cette forme que le théorème est énoncé dans le traité d'Eilenberg[1].

On peut employer le théorème pour prouver qu'un langage est rationnel en démontrant que la relation ${\displaystyle R_{L}}$ est d'index fini. Ceci se fait par une exploration systématique des mots à partir du mot vide : pour chaque mot, on cherche une classe déjà existante ou on crée une nouvelle classe. Par exemple, considérons le langage des mots binaires qui représentent des entiers divisibles par 3. Le mot vide (de valeur 0) et le mot 1 sont séparés par le mot vide, le mot 0 sépare le mot vide de 1. On a déjà trois classes correspondant aux nombres de reste 0, 1, et 2 modulo 3. Il reste à vérifier qu'il n'y a pas d'autre classe.

Un usage plus fréquent est la preuve qu'un langage n'est pas rationnel en montrant que l'index de la relation de Myhill-Nerode est infini. Si on prend par exemple le langage bien connu ${\displaystyle L=\{a^{n}b^{n}\mid n\geq 1\}}$, alors deux mots ${\displaystyle x=a^{n}}$ et ${\displaystyle y=a^{m}}$, avec ${\displaystyle n\neq m}$, sont séparables et séparés par le mot ${\displaystyle b^{n}}$ (ou ${\displaystyle b^{m}}$). Ainsi, ce langage n'est pas rationnel.

Le théorème de Myhill-Nerode se généralise aux arbres. Voir automate d'arbres.