Voir la source de Équivalence de Nerode

L''''équivalence de Nerode''' (ou '''congruence de Nerode''') est une [[relation d'équivalence]] sur les états d'un [[automate fini]] déterministe permettant de définir l'[[Minimisation d'un automate fini déterministe|automate minimal]] reconnaissant le même langage. Elle est nommée ainsi en l'honneur de [[Anil Nerode]].

== Définition ==
Soit <math>A</math> un [[alphabet]] et <math>\mathcal{A} = (Q, i, T)</math> un [[automate fini]] déterministe sur cet alphabet, où <math>Q</math> est l'ensemble des états, <math>T</math> est l'ensemble des états finaux, <math>i</math> est l'état initial. La fonction de transition est notée par un point.

Pour tout état <math>q \in Q</math> on note 
:<math>L_q = \{w \in A^*, q \cdot w \in T\}</math> 
l'ensemble des mots qui mènent de <math>q</math> à un état final. L''''équivalence de Nerode''' est la relation, notée <math>\sim</math>, sur l'ensemble des états définie par
:<math>q \sim q'\iff L_q = L_{q'}</math> .
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.

== Propriétés ==
Cette relation permet de définir un automate dont les états sont les classes d'équivalence induites par la relation <math>\sim</math>. 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.

{{Théorème|Propriété|Si <math>q \sim q'</math>, alors <math>q \cdot a \sim q' \cdot a</math> pour toute lettre  <math>a</math> .}}

En effet, <math>w \in L_{q \cdot a} \Leftrightarrow a w \in L_q</math>, or <math>L_q = L_{q'}</math>, donc <math>L_{q \cdot a} = L_{q' \cdot a}</math>.

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

L'automate ainsi obtenu est isomorphe à l'[[Minimisation d'un automate fini déterministe|automate minimal]] du [[langage rationnel]] reconnu par l'automate initial.

== Mise en pratique ==
Le calcul des classes d'équivalence peut être effectué avec l'[[Algorithme de Moore de minimisation d'un automate fini|algorithme de Moore]] ou l'[[algorithme de Hopcroft]].

== Bibliographie ==
* {{Langages formels, calculabilité et complexité}}<!--pour appeler cet ouvrage par un harv on peut faire par exemple {{harvsp|Carton|texte=Carton 2008}}-->
* Cours de Laurent Chéno en [[classes préparatoires]] ([[licence Creative Commons]] BY-NC-SA)

{{Portail|Informatique théorique}}

{{DEFAULTSORT:Equivalence De Nerode}}
[[Catégorie:Théorie des automates]]
[[Catégorie:Calculabilité]]