Algorithme de Conway

En informatique théorique, l'algorithme de Conway est un algorithme, en théorie des automates, qui calcule une expression rationnelle pour le langage accepté par un automate fini. Cet algorithme est décrit par John Horton Conway dans son livre Regular Algebra and Finite Machines^[1]. L'algorithme fait donc partie, avec l'algorithme de McNaughton et Yamada et la méthode de Brzozowski et McCluskey, des méthodes visant à donner une expression rationnelle pour un automate fini donné.

Principe

L'algorithme part d'une matrice contenant les transitions de l’automate. Le langage reconnu par l'automate est une union des coefficients de l'étoile de Kleene de la matrice. La particularité de l’algorithme de Conway est de calculer l'étoile de Kleene récursivement par une partition en blocs de la matrice. Dans le cas particulier où la partition consiste à choisir un bloc de taille 1, la méthode revient à l'élimination des états par le lemme d'Arden.

Description

Matrice de l'automate

É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

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^{*}}$

Calcul de Conway

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.

Relation avec les autres méthodes

La méthode d'élimination ou méthode de Gauss revient à partitionner les états en deux classes particulières, la classe {1, etc., n-1} et la classe composée de {n}. En revanche, il ne semble pas avoir de lien avec l'algorithme de McNaughton et Yamada.^{[réf. nécessaire]}

Notes et références

Bibliographie

• John H. Conway, Regular Algebra and Finite Machines, Londres, Chapman and Hall, 1971 (lire en ligne) — réimpression : Dover Publications, 2012, (ISBN 978-0486485836).

Articles liés

• Théorème de Kleene
• Méthode de Brzozowski et McCluskey
• Lemme d'Arden
• Algorithme de McNaughton et Yamada

• Portail de l'informatique théorique