Précédent Remonter Suivant
Chapitre 7 Machines finies et infinies

L e caractère fini d'un programme est une notion qui se retrouve tant dans les propriétés de terminaison, que dans celles de puissance d'expressivité. Un programme est la description finie d'un calcul. Cette simple remarque est à la base de la théorie de la calculabilité. Supposons qu'on puisse avoir droit à un nombre infini d'instructions. On n'aurait pas attendu des siècles pour connaitre la réponse à la conjecture de Fermat. Il aurait suffit d'exécuter en parallèle toutes les équations xn+yn = zn pour tous les quadruplets d'entiers positifs (x,y,z,n) (n > 2) en écrivant une astérisque sur l'imprimante si l'équation est vérifiée. Au bout d'un temps constant, si on ne voit rien écrit sur l'imprimante, la conjecture de Fermat est vraie. Pourtant, cette machine infinie semble irréaliste. Non seulement la taille du programme doit être finie, mais chaque donnée manipulée semble aussi devoir être bornée. Dans la vérification du théorème de Fermat, les nombres deviennent arbitrairement grands, et il semble illogique de donner un coût constant pour calculer la somme, l'exponentielle ou l'égalité de deux nombres arbitrairement grands. Enfin, la taille de la mémoire utilisée pour faire un calcul importe aussi. Peut-elle être infinie? Finie non-bornée? Doit-elle être bornée? Ce sont ces questions que nous abordons dans ce chapitre, en considérant deux modèles de machines: les automates finis et les machines de Turing. Il ne s'agira que d'une première approche vers la théorie de la calculabilité, inventée par Gödel, Church, Turing et Kleene. Cette théorie a de multiples rapports avec la théorie des langages formels associée à l'analyse syntaxique, ou avec la logique mathématique utilisée dans les propriétés de correction des programmes.

7.1 Exemples de machines finies

Nous commençons par passer en revue quelques exemples de machines à nombre d'états fini.
Exemple 1  Distributeur de café. La machine de la figure 7.1 comporte deux fentes pour les pièces de 10 et 20 centimes, et un bouton K pour obtenir un café. Au début, le bouton K est bloqué, les deux fentes sont ouvertes. Le café coute 30 centimes. Si on a mis suffisamment de pièces, les fentes se ferment, le bouton K est libéré, on ne peut plus mettre de pièces, et on peut enfoncer le bouton K. Alors un gobelet tombe dans l'espace vide au bas de la machine, et le café se verse dans le gobelet. L'automatisme correspondant comporte 4 états. Dans les états 0, 1, 2, les fentes sont ouvertes, le bouton K est bloqué. Dans l'état 4, les fentes sont fermées, le bouton K est débloqué. Les états 0, 1, 2, 3 enregistrent le crédit courant en multiples de 10 centimes. On passe d'un état à un autre soit en insérant une pièce dans une des deux fentes, soit en appuyant sur le bouton K. Au début, le distributeur est dans l'état 0. Ceci est résumé par le schéma à droite sur la figure  7.1.


Figure 7.1 : L'automate d'un distributeur de café



Exemple 2  Distributeur de café avec un tampon de longueur 2. L'appareil précédent ne rend pas la monnaie. Il n'autorise pas de mettre plus de 30 centimes avant que le café ne soit versé. Nous l'améliorons légèrement. On peut maintenant obtenir jusqu'à deux cafés consécutivement à condition d'avoir mis 60 centimes. Pour aller plus vite, la machine libère le bouton K dès que suffisamment de pièces ont été introduites. Ainsi on peut mettre deux pièces de 20 centimes, appuyer sur K, puis remettre deux autres pièces de 20 centimes, et une de 10 centimes, puis appuyer deux fois de suite sur K, etc. Au total, notre automatisme a maintenant les 7 états décrits sur la figure 7.2.


Figure 7.2 : L'automate d'un distributeur de café avec mémoire


Les mécanismes de nos deux machines à café sont simples, ils décrivent le fonctionnement d'un compteur sur un intervalle fini. L'intérêt de cette description est qu'on peut se contenter de l'automate pour chacune de ces machines. Ce n'est pas la peine de disposer d'un compteur. De simples dispositifs matériels peuvent réaliser notre automate. Il y a peu d'états, peu de transitions, le tout est bien sûr fini. On dit que l'automate décrivant notre machine est un automate fini. Beaucoup d'automatismes de la vie courante (feux rouges, barrières, etc) sont des automates finis.

Les circuits logiques sont un autre exemple de machines finies. Les circuits ont une partie combinatoire (enchaînements de portes pour calculer une fonction booléenne) et une partie de contrôle fini pour assurer la séquence entre les parties combinatoires. Par exemple, un processeur commence le traitement d'une instruction machine après avoir fini celui de celle qui la précède.


Exemple 3  Additionneur binaire série. A partir d'un additionneur sur 1-bit ADD1, on fabrique un additionneur série sur n bits. La porte ADD1 a un fil d'entrée pour les entreés x et y sérialisées, et un autre fil d'entrée pour la retenue entrante cin et deux fils de sortie pour la somme résultat s et la retenue sortante cout. Pour faire un additionneur sur n bits, la retenue de sortie reboucle sur l'entrée (après amplification), et on suppose le dispositif synchronisé sur une horloge pour faire d'abord entrer cin et x, puis y, puis laisser sortir s et cout, comme indiqué sur la figure 7.3.

Les données x et y arrivent entrelacées sur un seul fil d'entrée. L'additionneur réagit à des données de la forme x0 y0 x1 y1... xn ynxi et yi sont les (i+1)-ème bit en partant de la droite dans la représentation binaire de x et de y. Le résultat produit est s0 s1 ... sn représentant en binaire la somme s de x et de y, en sortant d'abord le bit de poids faible s0, puis le suivant s1, etc. Sur la figure 7.4, le fonctionnement de l'additionneur sur n bits est décrit par un petit automate. Au début, on est dans l'état 0. Si on a x0 = 0, on évolue vers l'état 0x, sinon on va en 1x. Dans l'état 0x, si on a y0=0, on va en 0y et alors on envoie 0 comme résultat pour s0, et on revient dans l'état 0 pour lire x1, puis y1. On recommence le même raisonnement avec x1 et y1. Etc. Si dans l'état 0x, on a y0=1, on va en 1y et on envoie 1 comme résultat pour s0, et on revient dans l'état 0 pour aussi traiter x1, et y1. Etc.

Les états 0 et 1 sont des états où on lit un xi avec la retenue courante valant respectivement 0 ou 1. Les états vx et vy signifient que la valeur v a été accumulée en additionnant la retenue courante à la valeur respectivement de xi, ou de xi et yi. La transtion !v signifie que v est la valeur de si.

La description du fonctionnement de cette machine est proche de celui fait pour la machine à café. Il consiste encore à faire un calcul sur un domaine à peu de valeurs. Il est aussi très simple car le séquencement de l'additionneur est trivial. Dans le cas de circuits plus réalistes (par exemple un processeur avec plusieurs niveaux de pipeline), le nombre d'états peut être beaucoup plus grand.


Figure 7.3 : Additionneur série




Figure 7.4 : L'automate d'un additionneur série



Exemple 4  Analyseur lexical. Dans la section 2.5, le code d'un analyseur lexical a été présenté. Il consistait à trouver dans un chaîne de caractères des lexèmes comme ceux correspondants aux identificateurs, aux nombres, ou opérateurs utilisés dans les expressions arithmétiques. Le code de notre analyseur correspond exactement à l'automate fini de la figure 7.5. Dans l'état initial, on saute tous les caractères blancs (espace, tabulation, retour ligne). Si on rencontre une lettre, c'est le début d'un identificateur, c'est-à-dire une suite de lettres et de chiffres. On génère le lexème dès que le caractère courant n'est plus ni une lettre, ni un chiffre. Dans l'état 2, on génère le lexème correspondant à un nombre. Dans l'état 3, il s'agit d'un opérateur.


Figure 7.5 : L'automate d'un analyseur lexical



Exemple 5  Mots avec des nombres pairs de a et de b. Dans cet exemple, plus académique, il s'agit de reconnaitre les mots sur l'alphabet {a, b} contenant un nombre pair de a et de b. On considère l'automate de la figure 7.6. On démarre dans l'état 0 et on accepte un mot quand on revient à l'état 0 après avoir lu toutes ses lettres. Si on lit un a, on passe à l'état 1, si c'est un b on passe à l'état 2. L'état 1 signifie qu'on a lu un nombre impair de a et un nombre pair de b; l'état 2 veut dire qu'on a lu un nombre pair de a et un nombre impair de b. Si dans l'état 1, on lit un a on revient à l'état 0; si dans l'état 1, on lit un b, on passe à un état 3 (nombre impair de a et nombre impair de b); etc. Remarquer que la chaîne vide est acceptée puisque contenant un nombre nul de a et de b.


Figure 7.6 : Mots contenant un nombre pair de a et de b


7.2 Automate fini

Les exemples précédents sont des exemples d'automates finis. Cette structure a été définie dans les années 50; elle constitue le premier exemple de machine abstraite considérée dans ce chapitre. Un automate fini A est un quintuplet (Q, S, d, q0, F) où
  1. S est l'alphabet d'entrée sur lequel sont construits les mots à reconnaitre,

  2. Q est un ensemble fini d'états,

  3. q0 Î Q est l'état initial,

  4. F Ì Q est l'ensemble des états de fin,

  5. d est une fonction Q × S ® Q, dite fonction de transition.
L'automate est à tout moment dans un des états de Q; au début il est dans l'état q0. L'automate est une machine finie permettant de reconnaître des mots sur l'alphabet S. Pour un mot w de S*, au début, l'automate lit la première lettre a0 de w. Il passe donc dans l'état q1 = d(q0, a0). Puis il lit la deuxième lettre a1 de w et il passe dans l'état q2 = d(q1, a1), etc., jusqu'à qn-1 après avoir lu les n lettres du mot w. Si qn-1 Î F, le mot w est accepté par l'automate. Sinon, le mot w est refusé.

Dans l'exemple des mots avec un nombre pair de a et de b. On a S = {a, b}, Q = {0, 1, 2, 3 }, q0 = 0, F = { 0 }, et d donné par les formules suivantes:
d(0, a) = 1      d(1, a) = 0      d(2, a) = 3      d(3, a) = 2
d(0, b) = 2      d(1, b) = 3      d(2, b) = 0      d(3, b) = 1

Formellement, la fonction de transition d de type Q × S* ® Q devient la fonction d de type Q × S* ® Q, définie récursivement sur w comme suit:
d(q, e) = q          d(q, aw) = d(d(q,a),w)
Le langage T(A) reconnu par l'automate A est défini par:
T(A) = { w | d(q0, w) Î F }
Cette définition ne fait que formaliser la discussion précédente. A partir de q0, on doit finir dans un état de fin dans F. Traditionnellement les automates sont représentés par un graphe dont les sommets sont les états, les arcs sont étiquetés par la lettre permettant la transition. Les états de fin sont marqués par des sommets dont partent des flèches tiretées vers l'extérieur. L'état initial est également marqué par une flèche tiretée incidente.


Figure 7.7 : Un automate fini


Graphiquement, comme indiqué sur la figure 7.7, l'automate est une machine disposant d'une bande de lecture, d'une tête de lecture, d'un état courant q, et d'une fonction de transition d. Au début la tête de lecture est sous le premier caractère de la bande à gauche. A chaque transition, en fonction de son état interne et du caractère sous la tête de lecture, il évolue vers un nouvel état en se déplacant d'un caractère vers la droite. L'automte se déplace vers la droite en lisant tous les caractères de la bande, et on regarde l'état final pour voir s'il est dans F. Remarquons que la bande de lecture est non-modifiable.

La représentation d'un automate fini peut se faire en dur dans un programme. Plusieurs manières existent: avoir une variable explicite pour l'état (comme dans la fonction accepter suivante), faire coïncider le contrôle du programme avec l'état (certains points du programme correspondent aux valeurs de l'état, et on se branche à ces points du programme en fonction de l'état désiré), ou tabuler la fonction de transition comme dans la fonction accepter1 suivante.
static boolean accepter (String w) {
  int n = w.length();
  int q = 0;
  for (int i = 0; i < n; ++i) {
    char c = w.charAt(i);
    switch (q) {
    case 0: if (c == 'a') q = 1;
       else if (c == 'b') q = 2;
       else return false;
       break;
    case 1: if (c == 'a') q = 0;
       else if (c == 'b') q = 3;
       else return false;
       break;
    case 2: if (c == 'a') q = 3;
       else if (c == 'b') q = 0;
       break;
    case 3: if (c == 'a') q = 2;
       else if (c == 'b') q = 1;
       else return false;
       break;
    }
  }
  return q == 0;
}

static boolean accepter1 (String w, int[ ][ ] delta) {
  int n = w.length();
  int q = 0;
  for (int i = 0; i < n; ++i) {
    char c = w.charAt(i);
    q = delta [q][c];
  }
  return q == 0;
}

Toutefois, la solution qui consiste à tabuler la fonction de transition pose souvent un problème de place mémoire. En Java, un caractère est représenté sur 16 bits, le tableau peut donc avoir 65536 n éléments pour un automate de n états. Comme ce tableau est souvent creux, on a intérêt à le compresser. Dans notre exemple, c'est simple puisque seuls les caractères a et b importent, mais en général cela peut être plus ardu. Une solution potentielle consiste à faire des listes d'association pour chaque état, en adoptant une représentation proche de celle des graphes avec des tableaux de successeurs adoptée au chapitre 1.

7.3 Automates finis non-déterministes

La définition précédente des automates finis leur donne un comportement déterministe. A tout moment, une seule transition est possible en fonction de l'état q et de la lettre sous la tête de lecture a. Dans les automates non-déterministes, plusieurs transitions sont possibles.
Exemple 6  Mots avec deux a consécutifs. Il s'agit de reconnaitre les mots sur l'alphabet {a, b} contenant un facteur aa. On les reconnait par l'automate de la figure 7.8(i). Dans l'état initial 0, si le mot w à reconnaitre commence par b, on reste dans l'état 0; si la première lettre de w est un a, on a le choix d'aller en 0 ou en 1. Dans l'état 1, on passe à l'état 2 avec un a; avec un b, l'automate se bloque, aucune transition n'est possible. Etc. L'état 2 est le seul état de fin. Les mots acceptés sont tous ceux pour lesquels il existe une série de choix pouvant mener à l'état 2. Ce sont bien tous les mots contenant un facteur aa.


Figure 7.8 : Mots contenant deux a consécutifs: (i) à gauche l'automate non-détermiste, (ii) à droite, l'automate déterministe.


L'intérêt de la présentation non-déterministe des automates finis est que sa description est souvent plus succincte et naturelle qu'une version déterministe équivalente. Par exemple, les mots reconnus par l'automate non-déterministe de la figure 6(i) sont aussi reconnus par l'automate déterministe de la figure 6(ii). La présentation déterministe est légèrement plus compliquée, mais cela peut être plus compliquée encore comme dans l'exemple suivant.
Exemple 7  Mots avec a en avant-dernière lettre. Il s'agit de reconnaitre les mots sur l'alphabet {a, b} décrits par l'expression régulière (a +b)*a(a+b). On les reconnait par les automates de la figure 7.9. On remarque que l'automate non-déterministe correspond exactement à l'expression régulière, alors que l'automate déterministe implémente un système de registre à retard pour accepter le mot dans les états 2 ou 3.


Figure 7.9 : Mots contenant a en avant-dernière position: (i) à gauche l'automate non-détermiste, (ii) à droite, l'automate déterministe.


En fait, le nombre d'états devient encore plus grand si on cherche à reconnaitre les mots dont la n-ième lettre à partir de la fin est a.
Exercice 48   Trouver le nombre d'états pour l'automate déterministe reconnaissant les mots dont la 3-ième lettre à partir de la fin est a.

La définition formelle d'un automate fini non-déterministe A est pratiquement identique à celle des automates déterministes; seule la fonction de transition diffère. Donc un automate fini non-déterministe est un quintuplet (Q, S, d, q0, F) où
  1. S est l'alphabet d'entrée sur lequel sont construits les mots à reconnaitre,

  2. Q est un ensemble fini d'états,

  3. q0 Î Q est l'état initial,

  4. F Ì Q est l'ensemble des états de fin,

  5. d est une fonction Q × S ® 2Q est la fonction de transition.
Dans l'automate de l'exemple de la figure 7.8, on a S = {a, b}, Q = {0, 1, 2 }, q0 = 0, F = { 2 }, et d donné par les équations suivantes:
d(0, a) = {0, 1 }      d(1, a) = {2 }      d(2, a) = {2 }
d(0, b) = {0 }      d(1, b) = Ø      d(2, b) = {2 }
Comme dans le cas déterministe, la fonction de transition d peut être étendue en la fonction d de type Q × S* ® 2Q, définie récursivement sur w comme suit:
d(q, e) = { q }         d(q, wa) = {q'' | q'Î d(q,w),  q'' Î d(q',a) }
Le langage T(A) reconnu par l'automate A est défini par:
T(A) = { w | d(q0, w) Ç F ¹ Ø }

Pour écrire une fonction ndAccepter implémentant la fonction d'acceptation d'un automate fini non-déterministe, on peut écrire le programme non-déterministe suivant:
class NDAutomate {
  int q0;
  Liste[ ][ ] delta;
  Liste fin;
  NDAutomate (int q, Liste f, Liste[ ][ ]d) { q0 = q; delta = d; fin = f; }

  static boolean ndAccepter (String w, NDAutomate a) {
    int n = w.length();
    int q = a.q0;
    for (int i = 0; i < n; ++i) {
      int c = w.charAt(i);
      Liste e = a.delta [q][c];
      if (e == nullreturn false;
      int k = Math.max(1,
                   (int)(Math.ceil(Math.random() * Liste.longueur(e))));
      q = Liste.kieme(e, k);
    }
    return Liste.estDans(a.fin, q);
  }
}
qui utilise une fonction de tirage au sort pour choisir parmi les états possibles à chaque transition. On a également besoin des fonctions suivantes sur les ensembles d'états, réalisés ici par des listes:
class Liste {
  int val;
  Liste suivant;
  Liste (int v, Liste x) { val = v; suivant = x; }

  static int longueur (Liste x) {
    if (x == nullreturn 0; else return 1+longueur(x.suivant);
  }

  static int kieme (Liste x, int k) {
    if (k == 1) return x.val; else return kieme(x.suivant, k-1);
  }

  static boolean estDans (Liste x, int v) {
    if (x == nullreturn false;
    else return x.val == v || estDans(x.suivant, v);
  }
}
Si le résultat de ndAccepter est vrai, le mot donné en argument est bien accepté par l'automate. En revanche, si le résultat est faux, il n'est pas sûr qu'une exécution suivante ne puisse retourner vrai avec la même chaîne d'entrée. Mais, on peut aussi écrire la fonction suivante qui énumère tous les choix possibles et qui par énumération exhaustive donne une réponse exacte sur l'acceptation d'une chaîne de caractères par un automate fini non-déterministe.
static boolean ndAccepter (String w, Automate a) {
   return ndAccepterE (w, 0, a, a.q0);
}

static boolean ndAccepterE (String w, int i, Automate a, int q) {
  int n = w.length();
  if (i == n)
    return Liste.estDans(a.fin, q);
  else {
    boolean res = false;
    int c = w.charAt(i);
    for (Liste e = a.delta [q][c]; e != null; e = e.suivant) {
      int q1 = e.val;
      res = res || ndAccepterE (w, i+1, a, q1);
    }
    return res;
  }
}
Conformément aux méthodes exposées dans le chapitre 4, les appels récursifs de la fonction ndAccepterE consistent à faire des retours en arrière (backtracking) sur la chaîne d'entrée et revenir sur un choix différent.





Il existe bien d'autres formulations pour les automates finis en dehors des deux principales que nous venons de voir. En voici quelques unes qui s'obtiennent par variations sur la définition de la fonction d de transition:
  1. d : Q × S È {e} ® 2Q
    L'automate non-déterministe avec transitions vides peut à tout moment, dans l'état q avec la lettre a sous la tête de lecture, choisir entre faire une des transitions données par d(q,a), ou d'abord faire une transition vide qui change spontanément l'état en un état de d(q, e). Formellement
    d(q, e) = { q }  È  d(q, e)
    d(q, uav) = {q3 | q1Î d(q,u),  q2 Î d(q',a),  q3 Î d(q2,v) }


  2. d : Q × S* ® 2Q défini sur un sous-ensemble fini de S*
    L'automate fini non-déterministe avec transitions composées peut à tout moment choisir une des transitions données par d(q,u) si la lettre sous la tête de lecture est la première du mot u dans le mot à analyser. Bien remarquer qu'on exige que le nombre de transitions décrites par d est fini. Formellement
    d(q, e) = { q }  È  d(q, e)    si d(q, e) est défini
    d(q, e) = { q }    sinon
    d(q, vuw) = {q3 | q1Î d(q,v),  q2 Î d(q1,u),  q3 Î d(q2,w) }


  3. d : Q × S ® 2Q × {gauche, droite }
    L'automate fini non déterministe avec déplacement dans les 2 sens fonctionne comme un automate fini non-déterministe, sauf qu'après avoir lu une lettre, il peut se déplacer d'une case vers la droite, ou d'une case vers la gauche pour relire un caractère qu'il a déja lu. Si le déplacement vers la gauche n'est pas possible, l'automate se bloque. La condition d'arrêt est toujours que l'état obtenu soit dans F, mais il se peut qu'on n'ait pas lu tout le mot à reconnaitre. Formellement, nous considérons les configurations (u,q,v) où u est le mot (strictement) à gauche de la tête de lecture, v le mot à droite, et q l'état courant, ainsi que la relation binaire associée ¾® sur les configurations définie par
    (q', droite) Î d (q, a) Þ (u, q, av) ¾® (ua, q', v)
    (q', gauche) Î d (q, a) Þ (ub, q, av) ¾® (u, q', bav)
    Si ¾®* est la fermeture réflexive et transitive de ¾®, alors les mots acceptés par un tel automate sont les mots de
    T(A) = { w | (e, q0, w)
    *
    ¾®
     
    (u, q, v),  qÎ F }
On peut donc se poser le problème de l'expressivité de ces diverses définitions. En fait, on peut montrer qu'elles sont toutes équivalentes. Un ensemble de mots reconnu par l'une est aussi reconnaissable par l'autre. Nous laissons ces démonstrations en exercice. On pourra donc choisir entre ces définitions d'automates finis non-déterministes en fonction de la commodité d'utilisation.

7.4 Les trois théorèmes fondamentaux

La théorie des automates finis est riche. Nous ne ferons que l'aborder à travers les trois théorèmes suivants.
Théorème 1  [Rabin, Scott]   Les langages reconnus par les automates finis déterministes sont exactement ceux reconnus par les automates finis non-déterministes.

Démonstration  Trivialement les mots reconnus par un automate déterministe le sont aussi par un automate non-déterministe, puique les automates finis déterministes forment un cas particulier des automates non-déterministes. Réciproquement, si A est un automate fini non-déterministe (Q, S, d, q0, F), considérons l'automate
A' = (2Q, S, d', q0, F')
où 2Q est l'ensemble des parties de Q, où l'ensemble de fin F' vérifie
F' = { Q | Q Ç F ¹ Ø)
et la fonction de transition d' est définie, pour tout aÎ S et tout E Ì Q, par
d'(E, a) =
 
È
qÎ E
d(q, a)
Alors on montre facilement que les mots acceptés par A le sont aussi par l'automate déterministe A'.

Comme vu dans les exemples précédents, le nombre d'états peut être plus grand dans la version déterministe. En fait, on peut montrer qu'il peut devenir exponentiel. Le théorème précédent indique simplement que le non-déterminisme n'introduit pas un nouvel ensemble de langages reconnus. Toutes les définitions précédentes d'automates finis sont donc équivalentes.

Nous énonçons deux autres théorèmes sans démonstration.
Théorème 2  [Myhill, Nerode]   Tout langage reconnu par un automate fini est reconnu par un automate déterministe minimal unique à un isomorphisme près sur le nom des états.

Ce théorème dit que, pour tout langage reconnu par un automate fini, il existe un automate déterministe minimal canonique le reconnaissant. On peut donc déterminiser un automate non-déterministe et calculer ensuite l'automate minimal correspondant. Remarquons que le théorème n'est pas vrai pour les automates non-déterministes.
Théorème 3  [Kleene]   Les langages reconnus par un automate fini sont exactement ceux décrits par les expressions régulières.

Ce théorème, attribué un peu rapidement au promoteur des expressions régulières, Kleene, connecte la notion d'expression régulière et la notion d'automates finis. Ainsi les langages reconnus par des automates finis sont aussi appelés langages réguliers. On comprend donc mieux les analyseurs lexicaux du chapitre 2. Les programmes calculant les lexèmes décrits à partir d'expressions régulières étaient en fait des implémentations d'un automate fini (déterministe) les calculant. Le contrôle de ces programmes représentaient les états de cet automate. La mémoire utilisée pour calculer les lexèmes ne dépassait pas celle nécessaire pour représenter les états de ces automates; elle était donc constante, ou encore en O(1).
Exercice 49   Trouver un automate fini non-déterministe de n états dont la version déterministe a 2n états.

Exercice 50   Montrer que, si on change la définition d'automate fini (déterministe ou non-déterministe) pour autoriser plusieurs états initiaux, on reconnait encore le même ensemble de mots.

7.5 Machines de Turing

En 1936, Turing a défini une puissante notion de machine étonnament simple. Il s'agit de pratiquement la même définition que celle des automates finis (fonctionnant dans les deux sens), avec une différence importante: on peut écrire sur la bande de lecture.
Exemple 8  Mots anbn. Le langage à reconnaitre est l'ensemble des mots de la forme anbn (n ³ 0). Avec un automate fini, on peut montrer que c'est impossible. Avec une machine de Turing, on écrit sur la bande pour compter les nombres relatifs de a et de b. On suppose également une infinité de caractères blancs B derrière le mot à reconnaître. La machine de Turing a le fonctionnement suivant: on remplace le premier a par un X, puis on cherche le premier b à droite, on le remplace par un Y. On repart à gauche jusqu'à un X. Si juste à sa droite, on trouve un a, on le remplace à nouveau par un X et on repart à droite à la recherche d'un b, qu'on remplace par un Y, puis on repart à gauche. Etc. Si juste à droite de X, on avait trouvé un Y, on doit s'assurer qu'il n'y a plus que des Y sur la droite jusqu'au premier caractère blanc. Si c'est le cas, on accepte le mot; sinon on le refuse. Graphiquement, la figure 7.10 résume les états successifs que prend la bande. La tête de lecture est sous la lettre soulignée.

aaabbb
Xaabbb
Xaabbb
Xaabbb
XaaYbb
XaaYbb
XaaYbb
XaaYbb
XXaYbb
XXaYbb
XXaYbb
XXaYYb
XXaYYb
XXaYYb
XXaYYb
XXXYYb
XXXYYb
XXXYYb
XXXYYY
XXXYYY
XXXYYY
XXXYYY
XXXYYY
XXXYYY
XXXYYYB
XXXYYYBB

Figure 7.10 : Etats successifs de la bande d'une machine de Turing lors de la reconnaissance du mot a3b3.


Plus précisément, une machine de Turing est un 7-uplet M = (Q, S, G, d, q0,B, F) où:
  1. S est un alphabet d'entrée,

  2. G est un alphabet des symboles de la bande (S Ì G),

  3. B Î G - S est le symbole blanc,

  4. Q est un ensemble fini d'états,

  5. q0 Î Q est l'état initial,

  6. F Ì Q est l'ensemble des états de fin,

  7. d : Q × G ® Q × G × { gauche, droite } est la fonction de transition.
Le fonctionnement peut se deviner à partir de celui des automates finis déterministes. Le deuxième résultat renvoyé par d est le symbole qu'on écrit sous la tête de lecture, avant de faire le mouvement indiqué par le troisième résultat. La bande de lecture (et d'écriture) est supposée infinie vers la droite. Elle a une portion finie à gauche non blanche. A partir d'une certaine case, la bande est constamment blanche vers la droite. Au début, la machine est dans l'état q0, la tête de lecture est sur la première lettre d'un mot w placé sur la partie gauche de la bande. La machine accepte tout mot dès qu'un état de fin est atteint. (Tous les caractères de w ne sont pas forcément lus.) Formellement, un configuration est un triplet (u, q, v) où Graphiquement, une configuration est illustrée sur la figure 7.11.


Figure 7.11 : Configuration d'une machine de Turing.


Les transitions sont définies par la relation binaire suivante sur les configurations:
d (q, X) = (q', Y, droite) Þ (u, q, Xv) ¾® (uY, q', v)
d (q, B) = (q', Y, droite) Þ (u, q, e) ¾® (uY, q', e)
d (q, X) = (q', Y, gauche) Þ (uZ, q, Xv) ¾® (u, q', ZYv)
d (q, B) = (q', Y, gauche) Þ (uZ, q, e) ¾® (u, q', ZY)
Le langage reconnu par la machine M est le sous-ensemble de mots
T(M) = {w | wÎ S*,   (e, q0,w)
*
¾®
 
(u,q,v),  q Î F }
Un langage reconnu par une machine de Turing est dit récursivement énumérable pour des raisons que nous ne pouvons expliquer ici.

Pour l'exemple 8, on considère la machine de Turing M = (Q, S, G, d, q0,B, F) où S = {a, b}, G = {a, b, X, Y, B}, Q = {q0, q1, q2, q3, q4 }, q0 est l'état initial, F = { q4 }, et la fonction de transition d est décrite par le tableau à double entrée suivant:
  a b X Y B
q0 (q1,X,droite)     (q3,Y,droite)  
q1 (q1,a,droite) (q2,Y,gauche)   (q1,Y,droite)  
q2 (q2,a,gauche)   (q0,X,droite) (q2,Y,gauche)  
q3       (q3,Y,droite) (q4,B,droite)
q4          




Le principe de fonctionnement d'une machine de Turing est donc très simple: le nombre d'états est fini, on a une fonction de transition entre ces états avec la bande servant de mémoire annexe. Cela fait une grande différence par rapport aux automates finis, puisque la taille mémoire utilisée est a priori non bornée. Dans le cas de anbn, on se sert d'une mémoire en O(n). Tout le coté fini de la description d'un calcul est résumé dans les machines de Turing: états, alphabet d'entrée et de symbole de bande, partie non blanche de la bande. Pourtant, la programmation avec des machines de Turing est fastidieuse. Une des raisons provient de l'accès séquentiel aux données rangées en mémoire (c'est-à-dire sur la bande). On est donc en droit de se demander si en rajoutant des instructions, on va pouvoir calculer plus de fonctions et avec plus de confort.

Comme pour les automates finis, on peut écrire la fonction accepter d'acceptation d'un mot w par une machine M. On remarque qu'à la différence des automates finis, la bande est maintenant décrite par une chaîne de caractères modifiable de la classe StringBuffer. On note aussi que sa taille est augmentée dynamiquement grâce à la méthode append de la classe StringBuffer. On suppose également que cette opération est toujours possible, et qu'on dispose donc d'une mémoire de taille non bornée.
class Turing {
  final static int GAUCHE = 0, DROITE = 1;
  final static char BLANC = 'B';
  int q0;
  Liste fin;
  Action[ ][ ] delta;

  static boolean accepter (String w, Turing m) {
    StringBuffer bande = new StringBuffer (w);
    int tete = 0;
    int q = m.q0;
    while ( !Liste.estDans(m.fin, q) ) {
      char c = tete < bande.length() ? bande.charAt(tete) : BLANC;
      Action a = m.delta [q][c];
      if (a == nullreturn false;
      q = a.q;
      if (a.dept == GAUCHE && tete > 0)
        bande.setCharAt(tete--, a.c);
      else if (a.dept == DROITE && tete < bande.length())
        bande.setCharAt(tete++, a.c);
      else if (a.dept == DROITE && tete == bande.length()) {
        bande.append(a.c);
        ++tete;
      } else return false;
    }
    return true;
  }

class Action { int q; char c; int dept;  }

Exercice 51   Donner une machine de Turing qui reconnaisse les palindromes w formés de a et de b tels que w=wRwR est l'image miroir de w.

Exercice 52   Trouver une machine de Turing qui reconnaisse les mots bien parenthésés formés de a et de b.

Exercice 53   Donner une machine de Turing qui calcule le successeur x+1 de tout nombre binaire x.

Exercice 54   Donner une machine de Turing qui calcule la somme x+y de tous nombres binaires x et y.

Exercice 55   Soit S(n) le nombre maximal d'étapes pris par une machine de Turing (déterministe) à n états avant de s'arréter en partant d'une bande complètement blanche. Calculer S(n) pour n £ 4 (le castor affairé de Rado).
7.6 Autres définitions de machines de Turing

Plusieurs définitions alternatives existent pour les machines de Turing. Nous en considérons quelques unes:
  1. d : Q × G ® 2 Q × G × { gauche, droite }
    Les machines de Turing non-déterministes peuvent évoluer, dans tout état, au choix avec plusieurs transitions possibles. Formellement,
    (q', Y, droite) Î d (q, X) Þ (u, q, Xv) ¾® (uY, q', v)
    (q', Y, droite) Î d (q, B) Þ (u, q, e) ¾® (uY, q', e)
    (q', Y, gauche) Î d (q, X) Þ (uZ, q, Xv) ¾® (u, q', ZYv)
    (q', Y, gauche) Î d (q, B) Þ (uZ, q, e) ¾® (u, q', ZY)


  2. Machines de Turing avec la bande infinie à gauche et à droite. Les transitions sur les configurations sont alors définies par:
    d (q, X) = (q', Y, droite) Þ (u, q, Xv) ¾® (uY, q', v)
    d (q, B) = (q', Y, droite) Þ (u, q, e) ¾® (uY, q', e)
    d (q, X) = (q', Y, gauche) Þ (uZ, q, Xv) ¾® (u, q', ZYv)
    d (q, B) = (q', Y, gauche) Þ (uZ, q, e) ¾® (u, q', ZY)
    d (q, X) = (q', Y, gauche) Þ (e, q, Xv) ¾® (e, q', BYv)
    d (q, B) = (q', Y, gauche) Þ (e, q, e) ¾® (e, q', BY)


  3. Machines de Turing avec transitions immobiles.
    d : Q × G ® Q × G × { gauche, immobile, droite } Les transitions sont définies par la relation binaire suivante sur les configurations:
    d (q, X) = (q', Y, droite) Þ (u, q, Xv) ¾® (uY, q', v)
    d (q, B) = (q', Y, droite) Þ (u, q, e) ¾® (uY, q', e)
    d (q, X) = (q', Y, gauche) Þ (uZ, q, Xv) ¾® (u, q', ZYv)
    d (q, B) = (q', Y, gauche) Þ (uZ, q, e) ¾® (u, q', ZY)
    d (q, X) = (q', Y, immobile) Þ (u, q, Xv) ¾® (u, q', Yv)
    d (q, B) = (q', Y, immobile) Þ (u, q, e) ¾® (u, q', Y)


  4. Machines avec n bandes. M = (Q, S, G, d, q0,B, F) est construit à partir de n machines Mk = (Qk, S, G, dk, qk0,B, Fk) à une seule bande en considérant:
    1. Q = Q1 × Q2 × ... Qn,
    2. d (q1, q2, ... qn) = (d1(q1), d2(q2), ... dn(qn)),
    3. q0 = q10 × q20 × ... qn0,
    4. F = F1 × F2 × ... Fn,

    Au début, le mot w à droite de la première tête de lecture, et les autres bandes sont blanches. Une n-configuration est un n-uplet de configurations (c1, c2, ... cn) où ck est une configuration de Mk pour 1 £ k £ n. La relation de transition devient
    (c1, c2, ... cn) ¾® (c'1, c'2, ... c'n)
    ck ¾®k c'k et ¾®k est la relation de transition sur les configurations de Mk.

  5. Machines de Turing avec transitions composées.
    d : Q × G* ® 2 Q × G* × { gauche, droite } défini sur un sous-ensemble fini de G*
    C'est une machine non déterministe dont les transitions sont exactement les mêmes que dans le cas non-déterministe en remplaçant partout X par un mot non vide x Î G+ et Y par un mot y Î G.
On peut montrer que toutes ces définitions sont équivalentes. Donc si un mot w est accepté par l'une de ces machines, il l'est aussi par une machine d'une autre sorte. Ces équivalences sont anecdotiques; leurs démonstrations sont intéressantes pour apprendre la technique de manipulation des machines de Turing. Philosophiquement, il apparait que le modèle de machine de Turing résiste bien aux extensions.
Exercice 56   Ecrire la fonction accepter d'acceptation d'un mot par une machine de Turing non-déterministe (selon la première définition de machine non-déterministe).

Exercice 57   Montrer que les 5 définitions de machines de Turing considérées reconnaissent les mêmes langages.

7.7 Thèse de Church

Dans les années 1920-1930, à la suite des résultats de Gödel, plusieurs modèles de la calculabilité ont été introduits: le l-calcul de Church, les fonctions récursives de Kleene, les machines de Turing, les systèmes de réécritures de Post. Ces modèles, quoique très différents dans leur présentation, ont tous été montrés équivalents. Ce qu'on calculait dans le calcul de Church pouvait être aussi calculé avec les machines de Turing, ou s'exprimait aussi avec une fonction récursive à la Kleene, et réciproquement. Church a donc émis le postulat suivant:
Thèse 1  [Church]   Tous les modèles de la calculabilité sont équivalents.

Cette hypothèse, parfois aussi attribuée à Turing (élève de Church), stipule qu'il y a un modèle unique de la calculabilité. Ce que l'on peut calculer avec une machine de Turing peut aussi être calculé en Java sur un PC; tout ce qui peut être calculé sur un PC peut être calculé sur un Mac; tout ce qu'on peut calculer en Java peut être aussi calculé en Ocaml, et réciproquement. Quelque soit le langage de programmation (Java, ML, Ocaml, Ada), on calcule les mêmes fonctions. Quelquesoit la machine support (PC, Mac, Alpha, HP), on calcule les mêmes fonctions. Le modèle unique de la calculabilité repose sur des hypothèses fortes de représentation finie du calcul, et sur rien de plus.

Pourtant, ce qui est calculé avec un automate fini est strictement moindre que ce qu'on peut faire avec une machine de Turing. Nous avons cité l'exemple du langage {an bn | n ³ 0 } reconnaissable par une machine de Turing, mais pas par un automate fini. Bien d'autres exemples existent. La raison profonde provient de l'espace mémoire borné seulement disponible avec un automate fini. En effet, à partir d'un certain n, il sera impossible de se souvenir du nombre de a rencontrés dans le mot anbn, et donc impossible de compter le nombre identique de b. Une machine de Turing dispose d'un espace mémoire non-borné grâce à sa bande (réinscriptible). C'est cela qui donne plus de puissance à une machine de Turing.

Traditionnellement, on utilise la thèse de Church en informatique sans montrer dans les détails qu'un langage de programmation ou un modèle de machine peut être codé en une machine de Turing. Si le raisonnement est parfaitement exact au niveau d'un langage de programmation puisqu'on peut toujours le compiler vers du code exécutable par une machine de Turing, on peut plus douter de l'argument pour comparer un ordinateur moderne à une machine de Turing. Un ordinateur dispose-t-il d'une mémoire non bornée? Les réponses peuvent diverger: les pragmatiques diront que la mémoire centrale est bornée, les idéalistes diront qu'on peut toujours rajouter de la mémoire externe (disques, bandes), autant que nécessaire, les ultra-sceptiques diront que le nombre d'atomes de l'univers est borné et qu'on ne peut donc disposer d'une mémoire arbitrairement grande. En règle générale, s'il est vrai qu'on peut comparer un ordinateur à un automate fini, le nombre d'états sera très grand et une bonne approximation consiste à prendre le modèle d'une machine de Turing.
Exercice 58   Montrer qu'une machine de Turing qui n'écrit que sur une partie bornée de la bande est équivalente à un automate fini.

Si nous avons vu qu'un modèle très simple suffisait pour faire tous les calculs imaginables, il n'est absolument pas garanti que l'écriture de programmes soit commode dans le modèle simplifié. Au contraire, on a besoin de langages de programmation de haut-niveau pour avoir une écriture plus concise. Par ailleurs, on peut se demander si on sait calculer toute fonction des mathématiques, ou s'il existe des fonctions non-calculables.

Depuis Gödel, nous savons qu'il existe des objets non-calculables. Un argument savant consiste à dire qu'il existe un nombre dénombrable (À0) de machines de Turing, alors qu'il y a un bien plus grand nombre (À1) de langages sur l'alphabet S. Un tout simple argument par diagonalisation donne ausi la solution. Comme les programmes ont une description finie, on peut les énumérer, c'est-à-dire trouver une fonction f de N dans les machines de Turing tel que f(i) = Mi est la i-ème machine de Turing. De même, on peut énumérer tous les mots sur un alphabet S avec une fonction y(i) = wi est le i-ème mot. On peut donc parler de la i-ème machine et du i-ème mot. Considérons l'ensemble
L = {  wi  |  wi ÏT(Mi)  }
Alors L ne peut être reconnu par une machine de Turing. Sinon, il existerait une machine Mk telle que L = T(Mk), et on aurait wk Î T(Mk) si et seulement si wk ÏT(Mk). Contradiction.
Théorème 4  [Gödel]   Il existe des langages non reconnaissables par une machine de Turing.


Supposons que nous disposions d'une représentation n pour tout entier naturel n. Par exemple, n sera la chaîne de caractères en représentation décimale donnée par l'expression Integer.toString(n) de Java. On peut alors parler de fonctions calculables sur N par machines de Turing. En effet, nous considérerons les fonctions fi définies par
fi(n) = m     ssi      (e, q0,
n
)
*
¾®
 
(
m
,q,v)    (q Î F)
pour la i-ème machine Mi = (Q, S, q0, F, d). Au début, on met n sur la bande, et, à la fin (si le calcul termine),on ne considère le résultat comme un entier que si une représentation d'entier m figure à gauche de la tête de lecture. Si ce n'est pas le cas, la fonction n'est pas définie pour n. La fonction fi n'est donc pas forcément définie pour tout n, soit parce que la machine de Turing correspondante ne termine pas, soit parce qu'elle retourne un résultat non entier sur sa bande. Au total, la fonction fi est donc une fonction calculable de type N ® N. Par la thèse de Church, ce sont aussi toutes les fonctions calculées en Java par une fonction de signature:
static int f (int n) { ... }

(en se restreignant aux arguments et résultats positifs). A nouveau, il existe plein de fonctions de N dans N non calculables, puisque le nombre de programmes écrits en Java est dénombrable. Plus généralement, on peut aussi définir des fonctions calculables sur d'autres domaines que N, mais la théorie demande plus d'habileté.
Exercice 59   Montrer rigoureusement qu'il existe des fonctions sur N non calculables.

7.8 Indécidabilité de l'arrêt

Parmi les fonctions non calculables, la fonction décidant de l'arrêt est célèbre. Il s'agit de tester si une machine M s'arrête avec un mot w donné sur la bande dans l'état initial. Pour les fonctions calculables, cela revient à trouver si f(n) est défini pour un n donné. Turing a montré que c'était impossible. Faire la démonstration avec les machines de Turing est un peu délicate, car faisant appel à des notions avancées de la théorie de la calculabilité. Nous en considérons une version simplifiée sur des programmes Java.

Ecrivons e ¯ et e' ­ pour signifier que l'évaluation de l'expression e termine et que celle de e' ne termine pas. Supposons qu'il existe une fonction termine qui prend un objet o en argument et teste si sa méthode f (sans arguments) termine. On a donc
Turing.termine(o) = ì
í
î
true   si    o.f( ) ¯
false   si    o.f( ) ­
Dans le programme suivant, où le code de termine n'est pas précisé, l'impression finale donne donc true pour o1 et false pour o2, puisque o1.f() ¯ et o2.f() ­.
class Tur)ng&nBsp:{

  static boolean termine (Object o) {
    // La valeur retournée vaut true si o.f()
    // termine. Sinon la valeur retournée vaut false.
    // (le code n'est pas public car breveté par le vendeur)
} }

class Facile {
  void f () {  }
}

class Boucle {
  void f () {
    for (int i = 1; i > 0; ++i)
      ;
} }

class Absurde {
  void f () {
    while (Turing.termine(this))
      ;
} }

class Test {
  public static void main (String[ ] args) {
    Facile o1 = new Facile();
    System.out.println (Turing.termine(o1));
    Boucle o2 = new Boucle();
    System.out.println (Turing.termine(o2));
    Absurde o3 = new Absurde();
    System.out.println (Turing.termine(o3));
} }

Pour o3 le problème est plus complexe. En effet
Turing.termine(o3) = true    ssi    o3.f() ¯    ssi    Turing.termine(o3) = false
Contradiction! La fonction termine n'existe pas. Il peut sembler que la difficulté provient de l'impossibilité de regarder avec attention le code de la méthode f, puisqu'on ne peut que l'appliquer dans nos programmes. En fait, même en disposant du code de f, on ne peut toujours pas décider de la terminaison. L'argument peut être conduit rigoureusement sur les machines de Turing. Nous ne faisons que suggérer l'énoncé de l'indécidabilité de l'arrêt.
Théorème 5   Il n'existe pas de fonction calculable h telle que pour tout i et n, on a h(i, n) = 1 si fi(n) est défini, et h(i, n) = 0 si fi(n) n'est pas défini.

La théorie de la calculabilité est amusante. Elle apporte principalement des résultats d'impossibilité. Il y a pourtant quelques résultats positifs. En voici un donné en exercice.
Exercice 60   Trouver un programme auto-reproductible en Java, c'est-à-dire un programme dont le résultat (par impression sur la sortie) est son propre code.

7.9 Applications des automates finis à la concurrence

Parmi les applications des automates finis, un certain nombre d'entre elles consistent à faire des vérifications, principalement de programmes concurrents, par méthode exhaustive (encore dénommé model checking en anglais). Si ces méthodes sont parfois peu esthétiques, elles sont souvent beaucoup plus efficaces que d'autres méthodes de correction de programmes, utilisant la logique ou les méthodes formelles. Toutefois, elles se prêtent moins à la paramétrisation (et donc à la modularité) des preuves de correction.

Dans l'algorithme de Peterson, une configuration est représentée par le quintuplet (p, p', actif[0], actif[1], tour)p est le compteur ordinal dans le premier programme, p' est celui du deuxième programme, et actif[0], actif[1], tour sont les valeurs des variables de synchronisation. Il y a 5 points possibles dans le code de chacun des processus: pour t0, alors p=1 correspond au début du code, p=2 est le point du programme avant de mettre actif[0] à vrai (1 ici dans notre codage), p = 3 est le point du programme avant le test de actif[1], p=4 est le point avant le test du tour, p=5 est la section critique avant de remettre actif[0] à faux et de retourner en p=1; pour t1, alors p' prend les valeurs symétriques. La fonction de transition de l'automate est décrite ci-dessous. A chaque état, deux transitions sont possibles selon que le processus t0 ou t1 s'exécute. On vérifie sur l'automate de gauche qu'on n'atteint jamais un état de la forme ((   5  5,  -  -  -)).
 
L'automate complet a 25 × 8 = 200 états. Nous n'avons dessiné que les états accessibles depuis ((   1  1,  0  0  1)).
 
    (   1  -,  -  -  -) ® (   2  -,  1  -  -)
    (   2  -,  -  -  -) ® (   3  -,  -  -  1)
    (   3  -,  -  0  -) ® (   5  -,  -  0  -)
    (   3  -,  -  1  -) ® (   4  -,  -  1  -)
    (   4  -,  -  -  0) ® (   5  -,  -  -  0)
    (   4  -,  -  -  1) ® (   3  -,  -  -  1)
    (   5  -,  -  -  -) ® (   1  -,  0  -  -)
     
    (   -  1,  -  -  -) ® (   -  2,  -  1  -)
    (   -  2,  -  -  -) ® (   -  3,  -  -  0)
    (   -  3,  0  -  -) ® (   -  5,  0  -  -)
    (   -  3,  1  -  -) ® (   -  4,  1  -  -)
    (   -  4,  -  -  1) ® (   -  5,  -  -  1)
    (   -  4,  -  -  0) ® (   -  3,  -  -  0)
    (   -  5,  -  -  -) ® (   -  1,  -  -  -)

Figure 7.12 : Vérification par méthode exhaustive de l'algorithme de Peterson.


Exemple 9  Vérification de l'algorithme de Peterson. Souvent la correction de programmes concurrents se ramène à l'étude d'un nombre fini de cas, que l'on peut caractériser par un automate fini. C'est le cas de l'algorithme de Peterson considéré en 6.8 où l'exclusion des sections critique est caractérisée par l'inaccessibilité de certains états, comme expliqué sur la figure 7.12.

Nous considérons à présent deux protocoles d'échanges de messages sur les réseaux. Ces exemple sont un peu plus longs à expliquer. En fait il ne sont pas si éloignés de l'exemple précédent. Il s'agit d'échanger de manière sure des messages à travers un réseau. Nous considérons deux protocoles: un simple contrôle de flux et le protocole du bit alterné, dans le cas d'une liaison uni-directionnelle.
Exemple 10  Protocole réseau: contrôle de flux. Deux processus évoluent en parallèle reliés par un canal de communication. Le premier, l'émetteur, envoie sans cesse des messages m0, m1, m2, ... sur le canal à destination du deuxième processus, le récepteur, qui lit continument ces messages. Les deux processus doivent suivre un protocole de contrôle de flux pour éviter que le récepteur ne soit submergé une multitude de messages. L'émetteur émet un message (action !m), puis attend un accusé de réception envoyé par le lecteur (action ?a). Il peut alors recommencer à émettre un nouveau message à destination du lecteur. Le fonctionnement à deux états de l'émetteur est représenté à gauche sur la figure 7.13. Le processus de lecture lui attend un message émis par l'émetteur. Il le lit (action ?m), puis émet un accusé de réception vers l'émetteur (action !a). Il revient à l'attente de lecture du prochain message. Son fonctionnement est au centre sur la figure 7.13. Le système en entier, constitué de l'émetteur et du récepteur et du contenu du canal de communication, est résumé à droite sur la figure 7.13. Il a 4 états XYZX est l'état de l'émetteur, Y celui du récepteur, Z est le contenu du canal de communication, e signifie action de l'émetteur, r signifie action du récepteur.


Figure 7.13 : L'automate d'un simple contrôle de flux sur un réseau. (i) à gauche: l'émetteur; (ii) au centre: le récepteur; (iii) à droite: le système en entier


Le contrôle de flux est proche du contrôle considéré dans les files concurrentes vu en 6.5 ou encore dans le problème du producteur-consommateur de 6.10. Toutefois, il n'y a pas de mémoire commune pour assurer la communication; il faut envoyer des messages de l'émetteur au récepteur et réciproquement pour assurer la synchronisation.
Exemple 11  Protocle réseau: protocole du bit alterné. Le protocole précédent suppose qu'aucun message ne puisse se perdre. Or, les pertes de messages sont fréquentes sur un réseau (à un certain niveau de protocole). Il faut donc considérer le cas où le message mi émis se perd, alors le récepteur ne reçoit rien et ne peut envoyer d'accusé de réception. L'émetteur doit ré-émettre le message mi au bout d'un certain temps (time-out), jusqu'au moment où l'accusé de réception lui parvienne. Mais, il se peut que l'accusé de réception se perde aussi, et alors le récepteur va lire deux fois le même message mi. Pour éviter la duplication de la lecture d'un même message, le protocle du bit alterné consiste à utiliser un bit pour caractériser le message émis, et mettre le récepteur dans un mode où il attend un certain type de message pour lecture effective. Sur la figure 7.14, on trouve en haut à gauche l'automate décrivant le protocole de l'émetteur, en haut à droite celui du récepteur, en bas l'automate de tout le système (émetteur, récepteur, état du canal de communication). Chaque état XYZ de ce dernier automate est donné par l'état X de l'émetteur, l'état Y du récepteur, et le contenu Z du canal; l'action e veut dire action de l'émetteur, r veut dire action du récepteur, t veut dire dépassement de temps.


Figure 7.14 : L'automate du protocole du bit alterné sur une liaison uni-directionnelle. (i) en haut à gauche: l'émetteur; (ii) en haut à droite: le récepteur; (iii) en bas: le système en entier.


Dans l'état 0, l'émetteur envoie un message de type 0 et passe dans l'état 1. Dans l'état 1, l'émetteur attend un accusé de réception. S'il arrive, on le lit et l'émetteur passe à l'état 2. Si un dépassement de temps se produit, l'émetteur revient à l'état 0. Dans l'état 2, l'émetteur envoie un message de type 1 et passe dans l'état 3. Là, il attend un accusé de réception. S'il arrive, il le lit et passe dans l'état 0. Si un dépassement de temps se produit, l'émetteur revient à l'état 2.

Coté récepteur, au début, on est dans l'état 0. Le récepteur attend alors un message de type 0. S'il arrive, on le lit et on va à l'état 1. Si c'est un message de type 1 qui arrive, c'est un message dû à une ré-émission causée par un dépassement de temps, on le saute et on passe à l'état 3. Dans l'état 3, le récepteur émet un accusé de réception et passe à l'état 0. Dans l'état 1, après la lecture d'un message effectif de type 0, on émet un accusé de réception et on passe à l'état 2. Dans l'état 2, on attend un message de type 1 et on va à l'état 3. Si c'est un message de type 0 qui arrive, cela veut dire que c'est un message ré-émis dû à un dépassement de temps, on saute le message, et on revient à l'état 1 pour re-émettre un accusé de réception.

Sur l'automate du système tout entier, on voit comment le système évolue dans le temps en faisant progresser concurremment les deux automates de l'émetteur et du récepteur. Dans l'état XYZ, l'émetteur émet un message de type ë X/2 û, le récepteur est en attente d'un message de type ë Y/2 û. On vérifie donc qu'on ne lit jamais deux fois le même message mi, puisqu'il est lu la première fois, et sauté s'il est réémis. En fait le lecteur lit mi sur la transition de 100 à 11- et mi+1 sur la transition de 321 à 33-. L'émetteur lit l'accusé de réception sur les transitions de 12a à 22- et de 30a à 00-. Toutes les autres lectures de messages ou d'accusés de réception sont dues à des réémissions.

Le protocole du bit alterné a en fait une belle structure symétrique qui permet de le généraliser à des canaux de communication bi-directionnels. En outre, au lieu d'assurer le passage d'un seul message, on peut avoir un protocole sur une fenêtre de plusieurs messages, ce qui permet d'accélérer les vitesses de transmissions. Les automates de ces protocoles à fenêtres ont un bien plus grand nombre d'états.





Une toute autre classe d'exemples d'automates finis décrivant des fonctionnements concurrents est celle des automates cellulaires. Les automates cellulaires sont des automates finis dont on suppose les fonctionnements synchronisés par une même horloge. Le prototype des automates cellulaires est celui du jeu de la vie de Conway. Un exemple plus militaire est celui du peloton d'exécution, laissé en exercice (difficile).
Exercice 61  Le peloton d'exécution. Il y a une forte brûme et un vent violent ce matin sur le plateau. On ne voit rien, on n'entend rien. Le général convoque n-1 soldats, les aligne sur son coté, et veut les faire tirer tous en même temps. Le général et les soldats sont des machines synchrones. Ils réagissent tous en phase en ne tenant compte que des états de leurs deux voisins de gauche ou de droite. Il y a 3 types de machines: le général qui n'a qu'un seul voisin (le premier soldat), les soldats, le soldat en bout de chaîne qui n'a aussi qu'un seul voisin. Montrer qu'il existe une solution, avec un nombre fini d'états, indépendant de n, pour chaque machine. (Indication: supposer n=2k et trouver le soldat du milieu)

Précédent Remonter Suivant