3. Définition des automates d'état fini

3.1. Présentation

Nous allons étudier en détail un cas particulier de machine de Turing : les automates finis. Nous en donnerons d'abord une définition précise. Nous verrons ensuite les différents modes de représentation, leurs propriétés ainsi que les algorithmes permettant de les utiliser.

La théorie des automates finis commence avec l'article de S.C. Kleene [Kleene 56] paru en 1956. Dans cet article tant de fois cité, Kleene démontre le premier résultat de cette théorie. C'est à la fois le premier dans l'ordre chronologique mais aussi dans l'ordre d'importance. Nous verrons un peu plus loin ce théorème.

3.2. Définition

Un automate fini, très souvent appelé "automate d'état fini" [Perrin 95], ("finite-state machine", "finite automaton", "Rabin-Scott Automaton" [Ginzburg 68]) est une machine de Turing dont le ruban se déplace toujours vers la gauche et case par case. Ce ruban est infini à droite et fini à gauche. Par ailleurs, la tête de lecture de la machine se contente de lire des symboles et n'effectue aucune écriture.

Remarques :

1. Certains auteurs, dont [Watson 93a], définissent les automates par un 6-uplet (A, Q, E, I, F, μ) en ajoutant un ensemble E des ε-transitions. Dans notre définition, ces transitions sont définies par μ.
2. Dans beaucoup de définitions, l'ensemble I est réduit à un seul état.
3. μ est une fonction partielle, car elle n'est pas définie pour toutes les valeurs du domaine. Le plus souvent, pour les couples (symbole, état) qui ne sont pas explicités, elle est définie de la façon suivante : μ(a,q)=0 où 0 est un état qui n'existe pas. Ces transitions provoquent un arrêt de l'automate ainsi qu'une erreur. L'état 0 peut être considéré comme l'état d'erreur de l'automate.
4. Les transitions peuvent être aussi de la forme :
   (a_i, q_j, q_k) ≡ (a_i, q_j) → q_k ≡ μ(a_i, q_j)= q_k
   avec a_i ∈ A ; q_j, q_k ∈ Q ;
5. Toujours à propos des transitions, |(a_i, q_i, q_k)| < 2

Au départ, une phrase construite sur le vocabulaire de l'automate est inscrite sur le ruban d'entrée et est entourée de symboles ε. L'unité centrale se trouve dans un des états initiaux de I et la tête de lecture est placée devant le symbole le plus à gauche de la phrase. A partir de cette position, l'automate va exécuter son programme. Pour une configuration courante (a_i, q_j), l'automate applique une transition μ(a_i, q_j) → q_k, passe alors dans l'état q_k et déplace le ruban d'une case vers la gauche. L'automate tel qu'il est défini n'est pas forcément déterministe. Plusieurs transitions concurrentes sont donc parfois applicables. L'automate s'exécute jusqu'à ce qu'il arrive à une situation (a_t,q_n) pour laquelle il n'existe pas de transition permettant au programme de poursuivre son calcul. Il suspend alors son exécution. Si la configuration finale est telle que a_t = ε et q_n ∈ F alors la phrase inscrite sur le ruban est acceptée par l'automate. Dans tous les autres cas, elle est refusée.

Remarque : Une façon utile de regarder le non déterminisme est de considérer qu'il permet à un automate de "formuler des hypothèses". Si, dans un état donné, on ne sait pas quoi faire sur un certain caractère d'entrée, il existe plusieurs possibilités pour le choix de l'état suivant. Comme chaque chemin étiqueté par une chaîne de caractères et conduisant à un état d'acceptation est interprété comme acceptable, on fait confiance à l'automate non déterministe dès qu'il fait une hypothèse juste, quel que soit le nombre d'hypothèses fausses faites auparavant.

Attention, une transition d'un AFN ne peut concerner qu'un seul symbole de l'alphabet et non pas un mot. Par contre, l'automate est indépendant des étiquettes des états. Ils peuvent être numérotés de manière continue ou pas, correspondre à des termes ayant un sens dans le langage courant...

3.2. Représentation des AFN

Les automates, et en particulier leur fonction de transition, peuvent être représentés de plusieurs manières : par des graphes orientés ou des représentations matricielles.

Prenons comme exemple l'automate T={{a,b,c}, {1}, {6,9}, μ}. Soit μ sa fonction de transition :

• µ(a,1) = 2 ; µ(b,1) = 4 ; µ(a,2) = 5 ; µ(b,2) = 3 ; µ(c,2) = 2 ; µ(a,3) = 6 ; µ(b,3) = 4 ; µ(c,3) = 9 ; µ(c,4) = 5 ; µ(a,5) = 5 ; µ(a,5) = 6 ; µ(c,7) = 4

La fonction de transition est très souvent représentée par une "table de transition" (parfois aussi appelée "matrice de transition", "flow table" en anglais). Cette représentation est très commode du point de vue de l'implémentation informatique des AFNs. Les tables de transition sont des tableaux (ou des matrices) dont les colonnes correspondent aux symboles et les lignes aux états. La cellule (l_i,c_j) indique les transitions (a_i, q_j) → q_k. L'AFN étant susceptible d'être non déterministe, plusieurs états peuvent être présents dans une cellule (l_i,c_j). Les symboles ne donnant aucune transition depuis un noeud dans un certain état sont alors à "0" (transition vers un état inexistant). Cet état correspond à un état d'erreur. C'est cette forme qui est la plus souvent utilisée en programmation. Si on reprend l'AFN servant d'exemple, nous avons alors la table suivante :

Un AFN peut être aussi représenté par un graphe orienté et valué, appelé "diagramme de transition" ou "graphe de transition". Les noeuds correspondent aux états et les arcs représentent les transitions possibles (calculées par la fonction de transition) entre les états. Ces arcs sont étiquetés par le symbole permettant cette transition. Les états initiaux sont représentés par un noeud possédant une flèche entrante sans origine. Un état final est représenté par un noeud doublement cerclé.

L'automate T, présenté précédemment, peut être représenté par le graphe suivant :

On observant cet automate T, de manière intuitive, on peut noter que certains états ne sont pas particulièrement utiles. Prenons d'abord l'état 7. Cet état n'intervient que dans une seule transition (de 7 vers 4). Aucune transition n'est "dirigée" vers 7. Cela signifie que la machine de Turing ne pourra jamais se trouver en l'état 7. Par conséquent, cet état peut être supprimé (ainsi que la transition de 7 vers 4). Pour l'état 8, c'est pire puisqu'il est totalement isolé. Il peut donc lui aussi être supprimé. Enfin, avec l'état 9, la situation est un peu différente mais le résultat sera le même. Lorsque la machine sera dans l'état 9, plus aucune transition n'étant exploitable, elle sera forcément en échec. Donc, prendre la transition de 3 vers 9 sur "c" sera forcément un échec. Si on supprime 9 et cette dernière transition, le résultat sera totalement identique, c'est-à-dire que étant sur 3, si le ruban est sur un "c", aucune transition ne sera exploitable et donc la machine se mettra aussi en échec. En conclusion, les états 7, 8 et 9 ainsi que les transitions associées peuvent être supprimés. Nous obtenons alors le tableau et le diagramme suivants :

Nous verrons dans le suite que ce procédé de simplification d'automates peut être automatisé. Nous verrons les notions associées (état puit, source, accessible...) et les algorithmes adéquats (élagage...). Nous irons même plus loin en fusionnant les états jouant le même rôle.

Il existe aussi d'autres représentations possibles comme des matrices binaires associées à chacun des symboles...

Remarque. Dans certains cas, il est plus facile de représenter un groupe de transitions par une notation ensembliste. Par exemple, supposons que pour un état donné q_i, nous avons soit un passage à l'état q_j pour les symboles a_p et a_q soit une conservation de l'état courant pour les autres symboles de l'alphabet A. Ce type de transition s'écrit : (a_p, q_i) → q_j ; (a_q, q_i) → q_j ; (a₁, q_i) → q_i ; (a₂, q_i) → q_i ; ... Soit : (a_j,q_i) → q_i, ∀ i ∉ {p,q}. Pour simplifier l'écriture, nous aurons : ({a_p, a_q}, q_i) → q_j ; (A-{a_p, a_q}, q_i) → q__i.

Plus généralement, les symboles peuvent être regroupés sous différentes classes et l'automate possède des transitions en fonction de ces classes. Nous retrouvons ici la même simplification que nous avions utilisée pour les expressions rationnelles (nous verrons que cette similitude n'est pas un hasard).

Cette simplification dans la syntaxe se répercute aussi au niveau du diagramme d'états. Les quatre notations suivantes sont équivalentes (en considérant un automate sur l'alphabet {a,b,c,d}) :

Mais attention, dans tous les cas, une transition ne concerne qu'UN SYMBOLE de l'alphabet. Les notations précédentes permettent simplement de simplifier la représentation de l'automate. Dans les 4, les trois dernières sont des "simplifications visuelles" de la première.

3.3. Exemple d'exécution d'un AFN

Nous avons vu qu'un automate fini est un cas particulier de machine de Turing. Il est donc possible de simuler le fonctionnement de cette machine. Pour cela, le plus courant est d'utiliser le graphe des transitions. Prenons par exemple l'automate T₁ = {{1,2,3,4,5,6},{1},{6}, {(a,1) → 2, (b,1) → 4, (a,2) → 5, (c,2) → 2, (b,2) → 3, (a,3) → 6, (b,3) → 4, (c,4) → 5, (a,5) → 5, (a,5) → 6}} et étudions le mot "accaa" sur cet automate. N'ayant qu'un seul état initial, la configuration initiale est schématisé par le graphe suivant (en bleu, l'état courant de la machine ; la flèche indique la position de la tête de lecture de la machine sur le mot) :

A partir de cette configuration initiale (état 1, symbole "a"), la seule transition possible pour faire évoluer la machine est celle de 1 vers 2 sur "a". Donc, la machine passe dans la configuration (état 2, symbole "c"). De même, à nouveau, la seule transition possible est celle de 2 vers 2 sur "c". Donc, la machine passe dans la configuration (état 2, symbole "c"). De nouveau, la seule transition possible est celle de 2 vers 2 sur "c". Donc, la machine passe dans la configuration (état 2, symbole "a"). Maintenant, la seule transition possible est celle de 2 vers 5 sur "a". Donc, la machine passe dans la configuration suivante (état 5, symbole "a").

La configuration courante nous pose un problème. En effet, étant dans la configuration (état 5, symbole "a"), deux transitions peuvent être exploitées : celle de 5 vers 5 sur "a" ou celle de 5 vers 6 sur "a". Cette situation est une situation de non-déterminisme. Il faut donc choisir une transition en prévoyant éventuellement de revenir dans cette configuration pour en reprendre une autre. Prenons donc la transition de 5 vers 5. La machine passe alors dans la configuration (état 5, symbole "ε"). Or, 5 n'est pas un état final. La machine est donc dans une situation d'échec (plus de symbole et état non final).

Il convient donc de revenir en arrière pour reprendre la transition de 5 vers 6 dans la configuration (état 5, symbole "a"). La machine passe alors dans la configuration finale (état 6, symbole "ε").

Le mot proposé "accaa" est alors accepté par l'automate T₁. Il en est de même pour les mots "aba", "bcaaa", "acba", acbbcaaa"... Par contre, pour le mot "abaa" n'est pas accepté. En effet, au bout d'un certain nombre d'étapes, la machine se retrouve dans la configuration (état 6, symbole "a"). A ce moment, plus aucune transition n'est exploitable et il reste un symbole à étudier. La machine est en échec et le mot est refusé. De même, pour "abbb", la machine va se retrouver dans la configuration (état 4, symbole "b"). Dans cette configuration, à partir de 4, aucune transition sur "b" n'est disponible.

3.4. Configuration et action

Pour pouvoir exprimer de manière plus formelle le déroulement d'un programme sur un automate fini, il est nécessaire d'introduire les notions de configuration et d'action.

Les machines exécutant un automate fini qui, pour un mot m, terminent dans une configuration d'arrêt qui est une configuration finale sont en situation d'acceptation (le mot m est accepté par l'automate). Dans tous les autres cas de configuration d'arrêt, la reconnaissance échoue (le mot m est rejeté). En cas de non déterminisme, un mot est reconnu s'il existe au moins une configuration finale. Par contre, si toutes les configurations d'arrêt ne sont pas finales, la reconnaissance échoue.

Exemples, avec T₁ :

• ("accaa", 1) est une configuration initiale ;
• (ε, 6) est une configuration finale ;
• ("caa", 2) est une configuration intermédiaire.

Une action représente le passage d'une configuration donnée d'un AFN à une autre par l'application d'une transition de l'automate. Bien évidemment, pour les AFNs, il peut exister plusieurs actions différentes pour une même configuration de départ (non déterminisme).

Notations : C —+/T→ C' signifie C —k/T→ C' avec k ≥ 1 et C —*/T→ C' signifie C —k/T→ C' avec k ≥ 0.

Par exemple, si on reprend l'automate T1 avec le mot "accaa", nous obtenons les suites d'actions suivantes :

• (« accaa »,1) → (« ccaa »,2) → (« caa »,2) → (« aa »,2) → (« a »,5) configuration non-déterministe :
  • (« a »,5) → (ε,5) cette configuration d'arrêt n'étant pas une configuration finale, le mot n'est pas, pour l'instant, reconnu ;
  • (« a »,5) → (ε,6) cette configuration d'arrêt étant une configuration finale, le mot est reconnu.

Donc (« accaa »,1) —*/T₁→ (ε,6) (OK) et (« accaa »,1) —*/T₁→ (ε,5) (ECHEC)

Remarques :

• —+/T→ est la fermeture transitive de —T→ et —*/T→ est la fermeture réflexive et transitive de —T→.
• Parfois, il est possible de trouver l'utilisation d'une fonction partielle récursive μ* définie à partir de la fonction de transition μ sur A* × Q → Q telle que : μ*(ε,q)=q et μ*(aw,q) = μ*(w,μ(a,q)).
  Cette fonction est équivalente à la notion d'action : avec a ∈ A et w ∈ A*,
  μ*(aw,q) = q' ≡ (aw,q) —1/T→ (w,q')
  et μ*(w,I) = q_f ≡ (w,I) —*/T→ (ε,q_f).

jeudi, 27/05/04 14:12