Algorithme de Conway

Étant donné un automate fini, on suppose les états numérotés de ${\displaystyle 1}$ à ${\displaystyle n}$, où ${\displaystyle n}$ est le nombre d'états. On définit une matrice carrée M d'ordre n, dont les coefficients sont des ensembles finis de lettres : le coefficient ${\displaystyle M_{p,q}}$ d'indices ${\displaystyle p}$ et ${\displaystyle q}$ est l'ensemble des étiquettes des transitions de ${\displaystyle p}$ à ${\displaystyle q}$ dans l'automate :

${\displaystyle M_{p,q}=\{a\in A\mid (p,a,q)\in \delta \}}$

où ${\displaystyle A}$ est l’alphabet et ${\displaystyle \delta }$ est l’ensemble des transitions de l'automate. La matrice ${\displaystyle M}$ peut être élevée au carré par la formule usuelle : ${\displaystyle M_{p,q}^{2}=\bigcup _{1\leq r\leq n}M_{p,r}M_{r,q}}$. Les coefficients sont des ensembles de mots de longueur ${\displaystyle 2}$. Plus généralement, on note ${\displaystyle M^{k}}$ la ${\displaystyle k}$-ième puissance de la matrice ${\displaystyle M}$ : ses coefficients sont des ensembles de mots de longueur ${\displaystyle k}$, et le coefficient d'indice ${\displaystyle p}$ et ${\displaystyle q}$ est formé des mots de longueur ${\displaystyle k}$ qui étiquettent des chemins de ${\displaystyle p}$ à ${\displaystyle q}$. Il en résulte que la matrice ${\displaystyle M^{*}=\bigcup _{k\geq 0}M^{k}}$ a la propriété que son coefficient d'indice p, q est l'ensemble des mots qui sont des étiquettes de chemins de p à q. Le langage L reconnu par l’automate est donc ${\displaystyle L=\bigcup _{i\in I}\bigcup _{t\in T}M_{i,t}^{*}}$ où ${\displaystyle I}$ et ${\displaystyle T}$ sont les ensembles d'états initiaux et terminaux de l’automate. Les coefficients de ces matrices peuvent être vus comme des expressions rationnelles sur ${\displaystyle A}$.

Exemple

Un automate à états.

Pour l'automate à deux états de la figure, la matrice s'écrit

${\displaystyle M={\begin{pmatrix}a&b\\0&b\end{pmatrix}}}$.

On a

${\displaystyle M^{2}={\begin{pmatrix}aa&ab+bb\\0&bb\end{pmatrix}}}$.

Les expressions pour ${\displaystyle M^{*}}$ sont

${\displaystyle M^{*}={\begin{pmatrix}a^{*}&a^{*}bb^{*}\\0&b^{*}\end{pmatrix}}}$

Comme ${\displaystyle I}$={1} et ${\displaystyle T}$={1,2}, on a ${\displaystyle L=a^{*}bb^{*}+a^{*}=a^{*}b^{*}}$

La méthode repose sur la formule suivante [2]:

Si ${\displaystyle M={\begin{pmatrix}A&B\\C&D\end{pmatrix}}}$, avec ${\displaystyle A}$ et ${\displaystyle D}$ des matrices carrées, alors

${\displaystyle M^{*}={\begin{pmatrix}(A+BD^{*}C)^{*}&A^{*}B(D+CA^{*}B)^{*}\\D^{*}C(A+BD^{*}C)^{*}&(D+CA^{*}B)^{*}\end{pmatrix}}}$

On peut interpréter cette formule en considérant le graphe de l'automate. Quand ses états sont partitionnés en deux classes, la sous-matrice ${\displaystyle A}$ correspond aux arcs qui joignent deux éléments de la première classe, ${\displaystyle B}$ aux arcs de la première vers la deuxième classe, de même ${\displaystyle C}$ aux arcs de la deuxième vers la première, et enfin ${\displaystyle D}$ aux arcs entre deux états de la deuxième. L'expression ${\displaystyle (A+BD^{*}C)^{*}}$ décrit les chemins d'un élément de la première classe vers elle-même : ils se décomposent en sous-chemins qui sont soit un arc dans ${\displaystyle A}$, soit d'un chemin qui quitte la première classe, chemine dans la deuxième classe, puis revient vers la première; ceci est décrit par la formule ${\displaystyle BD^{*}C}$. Le tout peut être répété autant de fois qu'il faut.

La matrice de l’étoile se calcule plus aisément en calculant d'abord les sous-expressions ${\displaystyle U=(A+BD^{*}C)^{*}}$ et ${\displaystyle V=(D+CA^{*}B)^{*}}$. La matrice ${\displaystyle M^{*}}$ s'écrit alors

${\displaystyle M^{*}={\begin{pmatrix}U&A^{*}BV\\D^{*}CU&V\end{pmatrix}}}$.

Exemple

Reprenons l'automate précédent à deux états, la matrice s'écrit

${\displaystyle M={\begin{pmatrix}a&b\\0&b\end{pmatrix}}}$.

Les expressions U et V sont respectivement ${\displaystyle U=a^{*}}$et ${\displaystyle V=b^{*}}$ parce que ${\displaystyle C}$ est l'expression vide. Il en résulte que

${\displaystyle M^{*}={\begin{pmatrix}a^{*}&a^{*}bb^{*}\\0&b^{*}\end{pmatrix}}}$

comme dans le calcul précédent.