É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'automate minimal reconnaissant le même langage. Elle est nommée ainsi en l'honneur de Anil Nerode.

Définition

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

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

L q = { w ∈ A ∗ , q ⋅ w ∈ T } {\displaystyle L_{q}=\{w\in A^{*},q\cdot w\in T\}}

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

q ∼ q ′ ⟺ L q = L q ′ {\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.

Propriétés

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.

Propriété — Si q ∼ q ′ {\displaystyle q\sim q'} , alors q ⋅ a ∼ q ′ ⋅ a {\displaystyle q\cdot a\sim q'\cdot a} pour toute lettre a {\displaystyle a} .

En effet, w ∈ L q ⋅ a ⇔ a w ∈ L q {\displaystyle w\in L_{q\cdot a}\Leftrightarrow aw\in L_{q}} , or L q = L q ′ {\displaystyle L_{q}=L_{q'}} , donc L q ⋅ a = L q ′ ⋅ a {\displaystyle L_{q\cdot a}=L_{q'\cdot a}} .

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

L'automate ainsi obtenu est isomorphe à l'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 ou l'algorithme de Hopcroft.

Bibliographie

  • Olivier Carton, Langages formels, calculabilité et complexité, [détail de l’édition] (lire en ligne)
  • Cours de Laurent Chéno en classes préparatoires (licence Creative Commons BY-NC-SA)
  • icône décorative Portail de l'informatique théorique