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

modifier

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

Matrice de l'automate

modifier

É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 transitions 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 rationnelles 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

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

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

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

Bibliographie

modifier

Articles liés

modifier