Sommaire

  Position du sujet
 1. Algorithme
 2. Machines de Turing
 3. Automates à états finis déterministes
 Premiers exemples
 Homme, loup, chèvre, salade
 01, puis ad libitum
 Compter les zéros et les uns
  Références
  Index

Machines de Turing et automates Laurent Bloch

---

Position du sujet

Au début de la session de 2007 du cours d’algorithmes pour la biologie, il me fut demandé de parler des automates. Je suppose que cette idée avait été inspirée par la présence, au coeur du logiciel Blast, très utilisé par les biologistes moléculaires, d’un automate à états fini déterministe.

La théorie des automates est vaste et assez complexe. Il ne peut être question ici que de l'effleurer.

En 1936 Alan Turing, à la suite de Gödel, s'attaque à un problème de décidabilité : un système est décidable s'il existe une procédure effective pour distinguer les propositions démontrables des autres. Pour définir plus rigoureusement la notion de procédure effective, Turing élabore un modèle d'automate appelé par la suite machine de Turing, qui lui permet de préciser la notion d'exécution d'un algorithme.

Inventer des procédures effectives (des algorithmes) consiste à déterminer un enchaînement d'opérations élémentaires qui exécuteront les calculs nécessaires à la solution de problèmes pour lesquels existent des solutions calculables (il y a des problèmes sans solution et des solutions incalculables). La programmation est l'art de réaliser des algorithmes. Turing montre que son modèle de calcul est universel, c'est-à-dire que toutes les machines de Turing sont équivalentes. Il formule la thèse selon laquelle tout algorithme est calculable par une machine de Turing. Ces idées fondent la théorie de la programmation des ordinateurs. Il revient à von Neumann de concevoir en 1945 l'architecture générale des appareils concrets qui vont réaliser les calculs selon le modèle de Turing, architecture si élégante que les ordinateurs d'aujourd'hui sont encore construits, pour l'essentiel, selon ses principes.

À partir des années 1950, le développement de l'informatique engendra la recherche en linguistique de la programmation, essentiellement dévolue à l'invention de méthodes sûres et efficaces pour concevoir et réaliser des langages de programmation et les logiciels qui les implémentent, compilateurs et interprètes. C'est dans ce contexte qu'apparut une classe d'automates plus simples et moins universels que la machine de Turing, mais bien adaptés à la conception de compilateurs : les automates à états finis, ainsi qu'un autre type de formalisme, dont on montre qu'il est équivalent, les langages réguliers.

La capacité des langages réguliers à modéliser des textes quelconques et à engendrer des automates capables de reconnaître les textes conformes au modèle ne pouvait manquer de retenir l'intérêt des biologistes moléculaires, à la recherche de solutions informatiques pour analyser leurs séquences nucléotidiques et protidiques, dont on sait qu'elles peuvent être représentées par des textes, avec des alphabets de respectivement quatre et vingt lettres. D'où la présence dans Blast d'un automate à états fini, de la variété déterministe, abrégée en DFA, par opposition aux automates à états finis non déterministes, ou NFA.

---

1. Algorithme

Ces lignes (et quelques autres) doivent beaucoup à l'ouvrage de Thérèse Accart Hardin et Véronique Donzeau-Gouge Viguié [1], dont la lecture ne saurait être trop recommandée au lecteur avide d'explications claires d'idées complexes.

L'informatique est la science du traitement des données. Il s'agit, en partant d'informations connues appelée données, de faire élaborer par un agent exécutant des informations nouvelles appelées résultats. Un traitement est l'application d'une méthode de passage d'un ensemble de données D à un ensemble de résultats R : à toute donnée d de D on fait correspondre un élément r de R. Cette définition est inspirée de la notion mathématique de fonction.

La méthode de passage invoquée doit être adaptée à l'agent exécutant. Par exemple, pour l'opération « somme de deux nombres entiers », la façon d'obtenir à partir d'un couple de nombres leur somme sera décrite différemment selon que l'agent exécutant sera un être humain muni d'un crayon et de papier ou le processeur d'un ordinateur.

Le traitement des données doit être effectif, c'est-à-dire que la méthode de passage doit pouvoir aboutir pratiquement au résultat. Prenons un exemple, soit D l'ensemble des numéros d'immatriculation des voitures immatriculées en France. Les symboles utilisés sont des chiffres et des lettres. Les règles de formation des numéros d'immatriculation sont la syntaxe du langage. La sémantique d'un numéro est l'identité de la voiture qui le porte. Considérons R, l'ensemble des départements français. La correspondance qui, à tout numéro d'immatriculation bien formé, fait correspondre le département d'immatriculation de la voiture qui le porte est un traitement de D, on sait comment le réaliser. Par contre la correspondance qui, à tout numéro d'immatriculation bien formé, ferait correspondre la commune d'immatriculation de la voiture associée n'est pas un traitement de D, car on ne sait pas élaborer cette information à partir du numéro, bien qu'elle existe sûrement. Cette correspondance ne peut pas être décrite de manière effective, c'est-à-dire par un algorithme.

Un algorithme est la description, pour un exécutant donné, d'une méthode de résolution d'un problème, autrement dit d'une suite d'opérations qui fournissent le résultat cherché.

La description de la méthode, c'est-à-dire l'algorithme, doit être adaptée à l'exécutant chargé d'effectuer le traitement. L'exécutant sait effectuer un nombre fini d'actions, que l'on nomme ses primitives (ce sont par exemple les instructions du jeu d'instructions du processeur décrit ci-dessus). L'algorithme doit être constitué d'une combinaison de ces primitives. Pour construire toutes les combinaisons possibles de primitives, on démontre qu'il suffit de savoir réaliser l'enchaînement de deux primitives (effectuer une action à la suite d'une autre), la répétition d'une primitive donnée et le choix, pendant l'exécution d'un traitement, entre deux primitives selon le résultat d'un test.

Un algorithme fournit, pour un exécutant donné, la décomposition de la tâche à réaliser en primitives de l'exécutant.

---

2. Machines de Turing

Il importe de se convaincre (ce ne sera pas en un jour) que tous les programmes que nous pourrons écrire dans différents langages sont équivalents. La machine de Turing est un modèle d'automate dont on trouvera ci-dessous une description très terre à terre. Alonzo Church, le directeur de thèse d'Alan Turing à Princeton, pour approfondir la notion de fonction, invente le λ-calcul, dont on montre que les expressions bien formées sont équivalentes à des machines de Turing. Les langages fonctionnels dérivent étroitement du λ-calcul. L'architecture de von Neumann, conçue pour réaliser efficacement les traitements décrits par une machine de Turing, engendre les langages impératifs. Tout programme, fonctionnel ou impératif, destiné à être exécuté, sera traduit dans un langage impératif, le langage machine de l'ordinateur utilisé. La cohérence de l'informatique, et l'équivalence sémantique des programmes écrits en divers langages, qui assurent la validité de cette opération, sont le fruit non pas du hasard, mais d'une conception théorique originelle commune. Gödel, Church, von Neumann et Turing étaient tous à Princeton en 1936.

Le lecteur curieux trouvera en annexe ?? quelques précisions sur les liens entre le modèle de la machine de Turing, la définition axiomatique des nombres entiers et les fonctions récursives.

Description de la machine de Turing

Un modèle formel pour une procédure effective (pour décrire un algorithme) doit posséder certaines propriétés. Premièrement, chaque procédure doit recevoir une définition finie. Deuxièmement, la procédure doit être composée d'étapes distinctes, dont chacune doit pouvoir être accomplie mécaniquement. Dans sa simplicité, la machine de Turing (MT) déterministe composée des éléments suivants répond à ce programme :

• une mémoire infinie représentée par un ruban divisé en cases. Chaque case du ruban peut recevoir un symbole de l'alphabet défini pour la machine ;
• une tête de lecture capable de parcourir le ruban dans les deux sens ;
• un ensemble fini d'états parmi lesquels on distingue un état initial et les autres états, dits accepteurs ;
• une fonction de transition qui, pour chaque état de la machine et chaque symbole figurant sous la tête de lecture, précise :
  • l'état suivant ;
  • le caractère qui sera écrit sur le ruban à la place de celui qui se trouvait sous la tête de lecture ;
  • le sens du prochain déplacement de la tête de lecture.

La configuration d'une machine de Turing (MT) peut être représentée par un triplet (q, m, u) où q est l'état de la machine, m le mot qui apparaît sur le ruban avant la position de la tête de lecture, u le mot figurant sur le ruban entre la position de la tête de lecture et le dernier caractère non blanc.

Un arc du graphe de la fonction de transition peut être représenté par un quintuplet (qi, si, sj, x, qj) où :

• q_i est l'état de départ ;
• s_i est le symbole pointé avant l'exécution du cycle ;
• s_j est le symbole qui doit remplacer s_i ;
• x est un élément de {G, D, w} (G pour gauche, D pour droite, w pour un déplacement nul) ;
• q_j est l'état de fin de cycle.

Machine de Turing

Un modèle théorique.
 

Pour se donner une intuition de la chose, imaginons une MT (machine de Turing) avec un alphabet {0, 1, <espace>} ; notre MT fonctionnera selon un cycle qui consiste à passer successivement par les trois phases suivantes, puis à recommencer :

Phase de lecture -

La machine lit le contenu de la case courante et le transmet comme paramètre d'entrée à la fonction de transition.

Phase de calcul -

La valeur de la fonction de transition est calculée en fonction de l'état courant et de la valeur contenue dans la case courante.

Phase d'action -

L'action déterminée par la fonction de transition est effectuée ; elle comporte (éventuellement) une modification de la valeur contenue dans la case courante et un déplacement de la tête de lecture ; cette phase d'action est donc capable de produire des symboles.

Nous conviendrons d'utiliser le système de numération unaire (dérivé de celui que vous utilisez pour marquer les points au ping-pong, autrement dit « les bâtons ») et de séparer les nombres par des 0. Le nombre n sera représenté par n+1 bâtons, afin de pouvoir représenter 0. Pouvons nous avec ce système additionner deux nombres ?

Le ruban mentionne successivement les nombres m=3 et n=2. Pour les additionner il suffit que la tête de lecture lise successivement les quatre chiffres unaires qui constituent le nombre 3, dont la fin sera indiquée par l'occurrence du signe zéro. Il faudra alors supprimer le zéro et réécrire d'une case à droite les chiffres du nombre 2, jusqu'à la rencontre d'un signe zéro, qui subira le même traitement, puis il faudra supprimer encore un chiffre 1 pour obtenir 5 : en effet, chacun des nombres m et n est représenté, respectivement, par m+1 et n+1 chiffres 1, donc si nous nous contentons d'accoler les deux représentations, nous aurions m+n+2 chiffres 1, qui représenteraient m+n+1 alors que nous voulons m+n. L'écriture de la table des transitions constituera pour le lecteur un exercice amusant :

État	symbole	symbole	sens du	État	Commentaires
d'entrée	lu	écrit	déplacement	de sortie
q0	0	0	G	q0	Parcours vide
q0	1	1	G	q1	Début de m
q1	1	1	G	q1	Parcours de m
q1	0	1	G	q2	Fin de m
q2	1	1	G	q2	Parcours de n
q2	0	0	D	q3	Fin de n
q3	1	0	D	q4	Premier recul
q4	1	0	D	q5	Second recul
q5	1	1	w	q5	Fin

On peut doter sa Machine de Turing de l'alphabet fini de son choix. Son ruban peut être infini dans les deux sens ou dans un seul. Elle peut même avoir plusieurs rubans. On montre que ces diverses machines sont équivalentes.

---

3. Automates à états finis déterministes

Un automate (ou machine) à états fini est un modèle abstrait utilisé pour représenter le fonctionnement d'un programme ou de tout autre dispositif susceptible d'être décrit en termes d'états et de transitions entre des états (circuit électronique, ascenseur, machine à café...). Il est en ce sens similaire à une machine de Turing, et l'on montre que ces deux formalismes, sous certaines conditions (notamment de restriction à une mémoire de taille finie), sont équivalents.

Un automate fini est constitué d'états en nombre fini ; il passe d'un état à un autre par une transition ; le diagramme de l'automate décrit les transitions possibles.

La définition formelle d'un automate fini déterministe est constituée des cinq élements suivants :

1. un ensemble fini d'états, souvent noté Q ;
2. un ensemble fini de symboles, appelé alphabet et souvent noté Σ ;
3. une fonction de transition qui reçoit comme arguments un état de Q et un symbole de Σ et qui rend comme résultat un état de Q ; la fonction de transition est souvent notée δ ;
4. un état initial q₀, appartenant à Q ;
5. un sous-ensemble F de Q constitué des états finals, ou états acceptants.

soit le quintuplet A=(Q, Σ, δ, q₀, F).

L'automate évolue (passe d'état en état) en fonction d'un mot qui lui est soumis ; il comporte un état initial, à partir duquel sont parcourus des arcs de transition déterminés par les symboles successifs du mot soumis en entrée.

Le mot soumis à l'automate est une séquence de symboles d'entrée de l'automate. Nous dirons que le mot w est accepté par l'automate s'il existe un chemin, étiqueté par les symboles consécutifs de w, entre l'état initial et un des états acceptants de l'automate.

L'ensemble des mots acceptés par l'automate constitue le langage reconnu par l'automate. De façon similaire, un langage est dit reconnaissable s'il existe un automate qui le reconnaît.

Un automate à états fini est dit déterministe si, pour chaque état, il y a, pour chaque symbole en entrée, au plus une transition possible.

Il existe aussi des automates finis non déterministes, tels qu'à partir d'un état donné il peut y avoir zéro, une ou plusieurs transitions pour un symbole d'entrée donné. On démontre que pour tout automate fini non déterministe il existe un automate déterministe équivalent (qui reconnaît le même langage).

La définition de l'automate fini non déterministe est similaire à celle de l'automate déterministe, seule change la définition de la fonction de transition δ :

• pour l'automate déterministe, la fonction de transition δ reçoit comme arguments un état de Q et un symbole de Σ et elle rend comme résultat un état de Q :
  
  
  δ : Q × Σ → Q
• pour l'automate non déterministe, la fonction de transition δ reçoit comme arguments un état de Q et un symbole de Σ ou la chaîne vide notée є et elle rend comme résultat une partie de Q :
  
  
  δ : Q × (Σ ∪ {є} ) → P(Q)

Que le lecteur ne s'inquiète pas, nous introduirons incontinent des façons moins abstraites de représenter les automates finis :

• le diagramme de transition, une représentation par un graphe orienté où chaque état est représenté par un noeud du graphe et chaque transition par un arc ; les noeuds sont étiquetés par le nom de l'état correspondant et les arcs par le symbole qui a déclenché la transition entre le noeud d'origine de l'arc et son noeud d'arrivée ;
• la table de transition, qui est l'énumération dans un tableau des résultats possibles de la fonction δ.

Premiers exemples

Voici un premier exemple d'automate fini ; il représente le fonctionnement d'une porte, dispositif dont chacun sait qu'il comporte deux états : ouvert ou fermé. Chacun de ces deux états peut être un état initial.

porte ouverte ou fermée

Automate fini pour déterminer si une porte est ouverte ou fermée.
 

Notre automate suivant ressemble plus à ceux que nous trouverons en biologie informatique ; il aboutit à un état « succès » si le mot qui lui est soumis est « Nice », à l'état d'erreur autrement :

Nice

Automate fini pour reconnaître le mot Nice.
 

Pour se représenter la façon dont un tel automate traite un mot qui lui est soumis en entrée, pensons à un dispositif analogue au schéma de la machine de Turing () : la tête de lecture examine successivement chaque symbole du mot, et selon la valeur du symbole déclanche la transition appropriée.

Homme, loup, chèvre, salade

Voici un automate, emprunté à l'ouvrage classique de John E. Hopcroft et Jeffrey D. Ullman Introduction to Automata Theory, Languages and Computation[2], qui modélise la solution de la devinette classique : un homme H voyage avec un loup L, une chèvre C et une salade S. Il arrive au bord d'une rivière que l'on peut traverser en bateau, mais le nautonnier n'accepte que deux passagers à bord. Comment faire pour que chacun traverse sans que le loup ne mange la chèvre, ni que la chèvre ne mange la salade ?

Pour fixer les idées, disons qu'à l'origine de notre observation les quatre protagonistes de la traversée de la rivière, respectivement H, L, C et S, sont sur la rive gauche, et qu'il leur faut atteindre la rive droite. Un état du système sera représenté par une chaîne de caractères construite par la concaténation des symboles associés aux protagonistes installés sur la rive gauche de la rivière, suivis d'un tiret, suivi des symboles associés aux protagonistes installés sur la rive droite.

L'état initial sera donc noté HLCS-. Nous voulons atteindre l'état -HLCS, état acceptant.

Un arc du diagramme qui représente l'automate correspond à un changement d'état, soit concrètement à une traversée de la rivière. L'homme H est bien sûr à bord du bateau lors de chaque traversée. Les arcs seront étiquetés par le symbole, en caractère minuscule, soit du personnage qui accompagne l'homme lors de la traversée considérée, soit h lorsque l'homme traverse seul à bord.

Combien d'états distincts peut comporter notre automate ? C'est le problème du nombre des parties d'un ensemble, puisqu'il s'agit bien de décrire des états où une partie de l'ensemble de nos protagonistes est sur une rive, le complément de cette partie sur l'autre. Le nombre des parties d'un ensemble fini à n éléments est 2ⁿ, soit ici 2⁴=16 états possibles.

Quels sont les états que notre automate doit éviter ? Il ne faut pas laisser en tête à tête, si j'ose dire, L et C, ou C et S, ou les trois ensemble ; les états interdits sont donc LC-HS, HS-LC, HL-CS, CS-HL, CLS-H et H-CSL, et il reste alors 10 états possibles.

Voici le diagramme qui représente les deux solutions possibles. On remarque que cet automate permet aussi bien la traversée de la rive gauche à la rive droite que l'inverse, et que chaque changement d'état est réversible : ce n'est pas le cas général des automates que nous verrons dans la suite.

homme, loup, chèvre, salade

Automate fini pour traverser une rivière avec un loup, une chèvre et une salade.
 

01, puis ad libitum

Toujours emprunté à Hopcroft et Ullman, Introduction to Automata Theory, Languages and Computation[2], voici un autre exemple simple et qui commence à ressembler à ce que nous aurons à faire en biologie informatique.

Nous voulons construire un automate qui reconnaisse tout langage sur l'alphabet {0,1} de la forme :



soit, de façon plus informelle, w est une chaîne quelconque de 0 et de 1 avec au moins la séquence 01 quelque-part : 01, 11100010, 00100 conviennent.

Que pouvons-nous dire des états de notre automate ? Il doit examiner les conditions suivantes :

1. S'il a déjà « vu passer » la séquence 01, toute séquence ultérieure de 0, de 1 ou d'un mélange des deux satisfera la définition de notre langage, et notre automate sera désormais toujours dans un état acceptant.
2. S'il n'a pas encore « vu passer » la séquence 01, mais que le dernier symbole reçu était un 0, la réception d'un 1 satisferait la condition et à partir de cet instant il pourrait accepter toute séquence quelconque de 0 ou de 1.
3. S'il n'a pas encore « vu passer » la séquence 01 et que soit il est dans l'état initial, soit le dernier symbole reçu était 1, notre automate doit poursuivre l'examen des symboles d'entrée jusqu'à ce qu'il reçoive un 0, puis un 1.

À chacune de ces conditions correspond un état de l'automate. La condition 3 sera représentée par l'état initial, q₀. Si, dans cet état q₀, le symbole reçu suivant est 1, clairement nous n'avons pas encore reçu le moindre 0, alors il nous faut rester en q₀. Plus formellement, δ(q₀,1) = q₀.

Par convention, les états acceptants sont figurés dans le diagramme par un double cercle.

Juste 01...

Automate fini pour trouver 01.
 

Compter les zéros et les uns

Voici un problème un peu plus ardu : nous voulons un automate qui reconnaisse le langage suivant, toujours sur l'alphabet {0,1} :



Il s'agit de compter les 0 et les 1, modulo 2. Chaque état devra indiquer si le nombre de symboles 0 lus à l'instant considéré est pair ou impair, et si le nombre de symboles 1 lus de même est par ou impair. Notre automate aura donc quatre états :

q₀ :

on a lu un nombre pair de 0 et un nombre pair de 1 ;

q₁ :

on a lu un nombre pair de 0 et un nombre impair de 1 ;

q₂ :

on a lu un nombre impair de 0 et un nombre pair de 1 ;

q₃ :

on a lu un nombre impair de 0 et un nombre impair de 1 ;

q₀ est à la fois l'état initial et le seul état acceptant de l'automate. En effet, lorsqu'aucun symbole n'a été lu, nous avons lu zéro 0 et zéro 1, or zéro est pair.

Nb pair de 0 et de 1

Automate fini pour un nombre pair de 0 et de 1.
 

Regardons le diagramme ci-dessus et remarquons la chose suivante :

• chaque entrée d'un symbole 1 fait franchir à l'état de l'automate la ligne pointillée verticale, dans un sens ou dans l'autre ;
• chaque entrée d'un symbole 0 fait franchir à l'état de l'automate la ligne pointillée horizontale ;
• au début du processus, dans l'état q₀, nous sommes à gauche de la ligne pointillée verticale, et le nombre de 1 est pair (zéro en l'occurrence) ;
• si nous passons de q₀ à q₂ nous restons à gauche de la ligne pointillée horizontale et le nombre de 1 ne change pas, il reste pair ;
• que nous soyons en q₀ ou en q₂, si le symbole d'entrée suivant est 1, la transition suivante nous fera passer, respectivement, en q₁ ou en q₃ ; dans les deux cas nous nous retrouverons à droite de la ligne pointillée verticale et le nombre de 1 sera devenu impair ;
• de q₁ ou de q₃, si le nombre de 1 redevient pair, la transition suivante nous ramène à gauche de la ligne pointillée verticale ;
• de la même façon, les états au-dessus de la ligne pointillée horizontale sont ceux pour lesquels le nombre de 0 est pair, et ceux en-dessous de cette ligne sont ceux pour lesquels le nombre 0 est impair.

Ce raisonnement est une preuve informelle de la conformité de notre diagramme à la définition des états de l'automate.

Nous pouvons également représenter cet automate par sa table de transitions :

		0	1
* →	q0	q2	q1
	q1	q3	q0
	q2	q0	q3
	q3	q1	q2

À bientôt pour la suite des aventures des automates,

Des automates aux expressions régulières

!

---

Références

[1]

Thérèse Accart-Hardin Véronique Donzeau-Gouge Viguié. Concepts et outils de programmation. Interéditions, Paris, 1992.
Manuel et méthode d'un enseignement du CNAM, cet ouvrage introduit les concepts fondamentaux de la programmation avec un souci pédagogique qui ne nuit pas à la rigueur.

[2]

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Automata Theory, Languages, and Computation. Addison Wesley, 1979 – 2007.

---

Index

algorithme, ??, ??, ??, ??, ??, ??, ??, ?? alphabet, ?? automate à états fini déterministe, ?? non déterministe, ?? à états fini déterministe, ?? à états fini, ?? déterministe, ??, ?? non déterministe, ?? non déterministe, ?? Church, Alonzo, ?? DFA, see automate à états fini déterministe diagramme de transition, ?? fonction récursive, ??

information, ??, ?? langage reconnaissable, ?? reconnu par un automate, ?? langages réguliers, ?? machine de Turing, ??, ??, ??, ??, ??, ?? mémoire, ?? Neumann, John von, ?? Neumann, John von, ??, ?? NFA, see automate à états fini non déterministe procédure effective, ??, ?? Turing, Alan, ??, ??, ??, ?? table de transition, ??

---

Ce document a été traduit de L^AT_EX par H^EV^EA