Utilisateur:ManiacParisien/Brouillons/Bio

En informatique théorique, et tout particulièrement en théorie des langages formels, le problème de l'équivalence d'automates est de déterminer si deux automates acceptent (ou reconnaissent) le même langage. Ce problème s'inscrit dans le cadre plus général qui consiste à déterminer si deux mécanismes de reconnaissance (comme les machines de Turing ou des automates à pile) acceptent le même langage ou si deux procédés de production (comme les grammaires formelles ou des règles de réécriture) engendrent le même langage.

Équivalence d'automates finis

Deux automates finis sont équivalents s'ils acceptent le même langage. Plusieurs algorithmes existent pour décider si deux automates finis sont équivalents.

Un algorithme naïf

Étant donnés deux automates finis déterministes ${\mathcal {A}}_{1}$ et ${\mathcal {A}}_{2}$ sur un alphabet commun $A$ reconnaissant respectivement les langages $L_{1}$ et $L_{2}$, les constructions, sur les automates, des opérations booléennes sur les langages permettent de construire un automate ${\mathcal {A}}$ qui reconnaît la différence symétrique $L_{1}\ L_{2}\cup L_{2}\ L_{1}$. Ce ensemble est vide si et seulement si $L_{1}=L_{2}$. Le test revient donc à tester si le langage reconnu par l'automate ${\mathcal {A}}$ est vide.

Algorithme par minimisation et bijection

Étant donnés deux automates finis déterministes ${\mathcal {A}}_{1}$ et ${\mathcal {A}}_{2}$ sur un alphabet commun $A$, pour savoir s'ils reconnaissant le même langage, on minimise dans une première étape ${\mathcal {A}}_{1}$ et ${\mathcal {A}}_{2}$ et, dans une deuxième étape, on teste l'égalité des automates minimaux. En effet, il n'existe qu'un seul automates minimal, à isomorphisme près, pour une langage donné. Le test d'isomorphie se code comme suit. On teste l'égalité par la tentative de construire deux bijections, l'une étant la réciproque de l'autre, entre les deux automates minimaux ; dans le code suivant essaie de construire les fonctions $f$ et $h$ :

Bij $(q_{1}$,$q_{2})$
  si un seul de $f(q_{1})$ et $h(g_{2})$ est défini
  ou si $f(q_{1})$ et $h(g_{2})$ sont définis et f(q_1)\ne q_2
    retourner faux 
  si f(q1) et h(q2) ne sont pas définis
    f(q1) := q2; h(q2) := q1; 
    pour toute lettre $a\in A$ faire
      Bij $(\delta _{1}(q_{1},a),\delta _{2}(q_{2},a))$
    retourner vrai 

La procédure est appelée sur les états initiaux des deux automates

Algorithme de Hopcroft et Karp

John Hopcroft et Richard Karp ont décrit, dans un rapport technique paru en 1971 un algorithme pour tester l'équivalence de deux automates finis déterministes basé sur la construction d'une partition des états de l'union des deux automates. Le rapport technique n'a pas donné lieu à publication, le titre « A linear time algorithm ... » est trompeur parce que l'algorithme, qui utilise la structure de données union-find, n'est en fait pas linéaire.

Soient donnés deux automates finis déterministes ${\mathcal {A}}_{1}=(Q_{1},A,i_{1},T_{1},\delta _{1})$ et ${\mathcal {A}}_{2}=(Q_{2},A,i_{2},T_{2},\delta _{2})$ sur un alphabet commun $A$. On suppose que les ensembles d'états sont disjoints ($Q_{1}\cap Q_{2}=\emptyset$) et on pose $Q=Q_{1}\cup Q_{2}$.

Code

Le code de l'algorithme est le suivant :

equiv $(q_{1}$,$q_{2})$
  si  un seul de $q_{1}$ et $q_{2}$ est terminal
    retourner faux 
  $C_{1}$ = FIND$(q_{1})$ ; $C_{2}$ = FIND$(q_{2})$  
  $C$ = UNION$(C_{1},C_{2})$ 
  pour toute lettre $a\in A$ faire
    equiv $(\delta _{1}(q_{1},a),\delta _{2}(q_{2},a))$
  retourner vrai 

La fonction est appelée par

equiv $(i_{1}$,$i_{2})$

Exemple

La partition en classes évolue comme suit :

1|2|3|4|5|6|7 
15|2|3|4|6|7 
15|26|3|4|7 
15|236|4|7 
15|236|47

Les deux automates sont donc équivalents puisque chaque classe contient seulement des états terminaux ou seulement des états non-terminaux.

Bibliographie

• John Hopcroft et Richard Karp, « A linear algorithm for testing equivalence of finite automata », Technical Report, Berkeley, Univeristy of California, n^o TR 71-114,‎ décembre 1971.
• « Une contribution originale sur le problème classique de l'équivalence des langages », Actualité de l'ENS de Lyon, 3 février 2015
• Filippo Bonchi et Damien Pous, « Hacking nondeterminism with induction and coinduction », Communications of the ACM, vol. 58, n^o 2,‎ 2015, p. 87–95 (ISSN 0001-0782, DOI 10.1145/2713167, présentation en ligne).
• Filippo Bonchi et Damien Pous, « Hopcroft and Karp’s algorithm for non-deterministic finite automata », prépublication,‎ 2011 (HAL hal-00639716, lire en ligne, consulté le 4 décembre 2018).
• Gregory Kucherov, « Application de CLASS/UNION : Test d'équivalence de deux automates déterministes », Université de Marne-la-Vallée, 25 octobre 2011, p. 509-512 (PowerPoint).
• Daphne A. Norton, « Algorithms for testing equivalence of finite automata, with a grading tool for JFLAP », M. S. Project Report, Department of Computer Science - Rochester Institute of Technology, 22 mars 2009 (consulté le 4 décembre 2018).