Équivalence de Nerode

Soit ${\displaystyle A}$ un alphabet et ${\displaystyle {\mathcal {A}}=(Q,i,T)}$ un automate fini déterministe complet sur cet alphabet, où ${\displaystyle Q}$ est l'ensemble des états, ${\displaystyle T}$ est l'ensemble des états finaux, ${\displaystyle i}$ est l'état initial. La fonction de transition est notée par un point.

Pour tout état ${\displaystyle q\in Q}$ on note

${\displaystyle L_{q}=\{w\in A^{*},q\cdot w\in T\}}$

l'ensemble des mots qui mènent de ${\displaystyle q}$ à un état final. L'équivalence de Nerode est la relation, notée ${\displaystyle \sim }$, sur l'ensemble des états définie par

${\displaystyle q\sim q'\iff L_{q}=L_{q'}}$ .

Deux états équivalents sont aussi dits indistinguables. Ne pas confondre cette équivalence, définie sur les états, avec la relation de Myhill-Nerode, du théorème de Myhill-Nerode, qui est définie sur les mots.

Cette relation permet de définir un automate dont les états sont les classes d'équivalence induites par la relation ${\displaystyle \sim }$. Cet automate est l'automate minimal reconnaissant le même langage. La propriété suivante exprime que l'équivalence de Nerode est régulière à droite.

En effet, ${\displaystyle w\in L_{q\cdot a}\Leftrightarrow aw\in L_{q}}$, or ${\displaystyle L_{q}=L_{q'}}$, donc ${\displaystyle L_{q\cdot a}=L_{q'\cdot a}}$.

Il est commode de noter ${\displaystyle [q]}$ la classe de l'état ${\displaystyle q}$, et ${\displaystyle [P]}$ l'ensemble des classes des éléments de ${\displaystyle P}$. On peut alors définir un nouvel automate ${\displaystyle {\mathcal {A'}}=\{[Q],[i],[T]\}}$, où ${\displaystyle [Q]=Q/{\sim }}$ est l'ensemble des classes d'équivalences, et où pour ${\displaystyle c\in [Q]}$ et ${\displaystyle a\in A}$, l'état ${\displaystyle c\cdot a}$ est la classe d'équivalence commune à tous les ${\displaystyle q\cdot a}$ où ${\displaystyle q}$ est dans la classe ${\displaystyle c}$.

L'automate ainsi obtenu est isomorphe à l'automate minimal du langage rationnel reconnu par l'automate initial.

Le calcul des classes d'équivalence peut être effectué avec l'algorithme de Moore ou l'algorithme de Hopcroft.

• Olivier Carton, Langages formels, calculabilité et complexité, 2008 [détail de l’édition] (lire en ligne)
• Cours de Laurent Chéno en classes préparatoires (licence Creative Commons BY-NC-SA)

• Portail de l'informatique théorique