Site WWW de Laurent Bloch
Slogan du site

ISSN 2271-3905
Cliquez ici si vous voulez visiter mon autre site, orienté vers des sujets moins techniques.

Pour recevoir (au plus une fois par semaine) les nouveautés de ce site, indiquez ici votre adresse électronique :

Automates et machines de Turing
Article mis en ligne le 17 avril 2007
dernière modification le 18 septembre 2014

Machines de Turing et automates

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 cœur 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ù :

  • qi est l’état de départ ;
  • si est le symbole pointé avant l’exécution du cycle ;
  • sj est le symbole qui doit remplacer si ;
  • x est un élément de G, D, w (G pour gauche, D pour droite, w pour un déplacement nul) ;
  • qj 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.

Le lecteur désireux de « faire marcher » une machine de Turing pourra en trouver
des modèles interactifs sur le Web, par exemple celle écrite par
Hamdi Ben Abdallah
sur le site Interstices.


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 q0, appartenant à Q ;
  5. un sous-ensemble F de Q constitué des états finals, ou
    états acceptants ;

soit le quintuplet A=(Q, Σ, δ, q0, 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 2n, soit ici
24=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 :

w | w = x01y



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 :

 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.
 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.
  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, q0.
Si, dans cet état q0, le symbole reçu suivant est 1, clairement
nous n’avons pas encore reçu le moindre 0, alors il nous faut
rester en q0. Plus formellement, δ(q0,1) = q0.

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 :

L = w | w a un nombre pair de 0 et un nombre pair de 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 :

 q0 :

on a lu un nombre pair de 0 et un nombre pair de 1 ;
 q1 :
on a lu un nombre pair de 0 et un nombre impair de 1 ;
 q2 :
on a lu un nombre impair de 0 et un nombre pair de 1 ;
 q3 :
on a lu un nombre impair de 0 et un nombre impair de 1 ;

q0 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 q0, 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 q0 à q2 nous restons à gauche de la ligne pointillée horizontale et le nombre de 1 ne change pas, il reste pair ;
  • que nous soyons en q0 ou en q2, si le symbole d’entrée suivant est 1, la transition suivante nous fera passer, respectivement, en q1 ou en q3 ; dans les deux cas nous nous retrouverons à droite de la ligne pointillée verticale et le nombre de 1 sera devenu impair ;
  • de q1 ou de q3, 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


Ce document a été traduit de LATEX par HEVEA