Algorithme de Conway

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En informatique théorique, l'algorithme de Conway est un algorithme, en théorie des automates, qui permet de calculer une expression régulière 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 régulière pour un automate fini donné.

Principe[modifier | modifier le code]

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[modifier | modifier le code]

Matrice de l'automate[modifier | modifier le code]

Étant donné un automate fini, on suppose les états numérotés de à , où 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 d'indices et est l'ensemble des étiquettes des transitions de à dans l'automate :

est l’alphabet et est l’ensemble des transition de l'automate. La matrice peut être élevée au carré par la formule usuelle : Les coefficients sont des ensembles de mots de longueur . Plus généralement, on note la -ième puissance de la matrice  : ses coefficients sont des ensembles de mots de longueur , et le coefficient d'indice et est formé des mots de longueur qui étiquettent des chemins de à . Il en résulte que la matrice 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 et sont les ensembles d'états initiaux et terminaux de l’automate. Les coefficients de ces matrices peuvent être vus comme des expressions régulières sur .

Exemple
Un automate à états.

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

.

On a

.

Les expressions pour sont

Comme ={1} et ={1,2}, on a

Calcul de Conway[modifier | modifier le code]

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

Si , avec et des matrices carrées, alors

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 correspond aux arcs qui joignent deux éléments de la première classe, aux arcs de la première vers la deuxième classe, de même aux arcs de la deuxième vers la première, et enfin aux arcs entre deux états de la deuxième. L'expression 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 , 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 . 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 et . La matrice s'écrit alors

.
Exemple

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

.

Les expressions U et V sont respectivement et parce que est l'expression vide. Il en résulte que

comme dans le calcul précédent.

Relation avec les autres méthodes[modifier | modifier le code]

La méthode d'élimination ou méthode de Gauss revient à partitionner les états en deux classes particulières, la classe {1,...,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.

Notes et références[modifier | modifier le code]

  1. Conway 1971.
  2. Conway 1971, Chapitre 3. Kleene's theory of regular event and expressions, Theorem 4, p. 27-28.

Bibliographie[modifier | modifier le code]

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

Articles liés[modifier | modifier le code]

Théorème de Kleene