É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 modifier
Soit un alphabet et un automate fini déterministe sur cet alphabet, où est l'ensemble des états, est l'ensemble des états finaux, est l'état initial. La fonction de transition est notée par un point.
Pour tout état on note
l'ensemble des mots qui mènent de à un état final. L'équivalence de Nerode est la relation, notée , sur l'ensemble des états définie par
- .
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 modifier
Cette relation permet de définir un automate dont les états sont les classes d'équivalence induites par la relation . 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 , alors pour toute lettre .
En effet, , or , donc .
Il est commode de noter la classe de l'état , et l'ensemble des classes des éléments de . On peut alors définir un nouvel automate , où est l'ensemble des classes d'équivalences, et où pour et , l'état est la classe d'équivalence commune à tous les où est dans la classe .
![{\displaystyle [q]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/71e9e31fc0142be3459da4ac1e7f26b2cfeb310e)
![{\displaystyle [P]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/25d78ad4ad13872df07ac9b02a2574250a0e54fd)
![{\displaystyle {\mathcal {A'}}=\{[Q],[i],[T]\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/15938423de66ca683dfd68f853760bc6ceb8b972)
![{\displaystyle [Q]=Q/{\sim }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2515da8ad9936e475997b7100ee522505869bf38)
![{\displaystyle c\in [Q]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/128d67df0380f33e0a7fdb90d4e48470b9f05305)
L'automate ainsi obtenu est isomorphe à l'automate minimal du langage rationnel reconnu par l'automate initial.
Mise en pratique modifier
Le calcul des classes d'équivalence peut être effectué avec l'algorithme de Moore ou l'algorithme de Hopcroft.
Bibliographie modifier
- 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)
