Automates finis

Étudiés par Kleene au début des années 50, les automates finis furent auparavant utilisés par McCulloch et Pitts comme un modèle << neuronal >> de calcul et par Shannon  pour décrire le comportement d'un canal de communication. Ils constituent la classe la plus simple de machines abstraites.

Un automate fini est défini par la donnée d'un alphabet A, d'un ensemble fini d'états E, d'une relation de transition, sous-ensemble de $E\times A \times E$, d'un état initial $I\in E$ et d'un ensemble d'états finaux $F\subseteq E$. Une transition (e, a, e'), dite de l'état e vers l'état e' et étiquetée par le symbole a, est notée $e\stackrel{a}{\to} e'$. En termes de graphes, les automates sont des multigraphes étiquetés, les sommets étant les états, les arcs étant étiquetés par les symboles de l'alphabet. Un calcul de cet automate est une suite de transitions $I = e_{1} \stackrel{a_{1}}{\to} e_{2} \stackrel{a_{2}}{\to} \cdots \stackrel{a_{n-1}}{\to} e_{n}$ ; ce calcul est réussi si le dernier état, e_n, est un état final, et on dit alors que le mot $a_{1}a_{2}\cdots a_{n-1}$ est reconnu par l'automate fini.

 

Un langage X est régulier s'il existe un automate fini dont l'ensemble des mots reconnus est exactement X. On montre qu'il existe alors un automate fini déterministe et complet (c'est-à-dire, pour tout état, il existe exactement une transition par symbole de l'alphabet) reconnaissant X. Ces automates finis peuvent être vus comme des machines abstraites, parmi les plus simples, puisqu'elles n'utilisent pas de mémoire, dont le fonctionnement est facile à simuler à l'aide d'un programme.

Un automate fini déterministe dont les transitions sont étiquetées par des valeurs de type Object peut être implémenté au moyen des deux classes suivantes :

class Etat {
  private boolean acceptant;
  private Map transitions;

  Etat(boolean acceptant) {
    this.acceptant = acceptant;
    this.transitions = new HashMap();
  }

  void ajouteTransition(Object c, Etat q) {
    transitions.put(c, q);
  }
  boolean accepte() {return acceptant;}
  Etat transition(Object c) {
    return (Etat) transitions.get(c);
  }
}

class Automate {

  private Etat initial;

  Automate(Etat initial) {
    this.initial = initial;
  }

  boolean accepte(List s) {
    Etat q = initial;
    for (Iterator i=s.iterator(); i.hasNext() && q!=null;)
      q = q.transition(i.next());
    return q!=null ? q.accepte() : false;
  }
}

Si q est un état, q.accepte() indique si q est final, et q.transition(c) retourne l'état résultant de la transition issue de q et étiquetée par l'objet c. L'unique constructeur de la classe Automate spécifie un état initial. Si a est un automate, et si l est une liste d'objets, a.accepte(l) indique s'il existe un calcul étiqueté par les objets successifs de l, menant de l'état initial à un état final. Un automate est défini à l'aide de son état initial. Voici l'exemple correspondant à la figure 2.26 :

class AutomateTest {

  public static void main(String[] args) {
    Etat
      q0 = new Etat(false),
      q1 = new Etat(false),
      q2 = new Etat(true),
      q3 = new Etat(false);
    q0.ajouteTransition(new Character('a'), q0);
    q0.ajouteTransition(new Character('b'), q1);
    q1.ajouteTransition(new Character('a'), q3);
    q1.ajouteTransition(new Character('b'), q2);
    q2.ajouteTransition(new Character('a'), q2);
    q2.ajouteTransition(new Character('b'), q2);
    q3.ajouteTransition(new Character('a'), q3);
    q3.ajouteTransition(new Character('b'), q3);
    Automate a = new Automate(q1);

    String s = args.length==1 ? args[0] : "";
    List l = new ArrayList();
    for (int i=0; i<s.length(); i++)
      l.add(new Character(s.charAt(i)));
    System.out.println("chaîne \"" + s + "\" acceptée : "
                       + a.accepte(l));
  }
}