Automate avec transition vide

Difficulté

Facile 25%

Contenus

On a l’habitude de dessiner un automate avec transition vide, en figurant les états par des cercles, en indiquant l’état initial par une flèche entrante, les états acceptants par un double cercle ou une flèche sortante, et la transition de l’état q à l’état q’ en lisant la lettre α par une flèche allant de q vers q’ et étiquetée par α.

Un automate fini A avec epsilon transition (ou automate avec transition vide) est un triplet (Vt, Q, T) où

Vt est le vocabulaire de l’automate ;
Q est l’ensemble fini des états de l’automate ;
T : Q × (Vt ∪ ε) → Q, est une application partielle appelée fonction de transition de l’automate.

Notons que la notation q(α)→q’ devient ambiguë, puisqu’elle prend maintenant deux significations différentes suivant que α est considérée comme une lettre (ou comme le symbole ε) et il y aura alors une transition unique, ou comme un mot (de longueur 1 ou 0), et il pourra alors y avoir un nombre arbitraire de transitions (dont au plus une sera non-vide).

À nouveau, les notions de dérivation est inchangée, et celle d’arbre de dérivations
ne nécessite qu’une adaptation triviale, du fait qu’il existe maintenant des transitions étiquetées par ε. Les calculs d’un automate avec transition vides autorisent le passage par un nombre quelconque de transitions vides au cours de l’exécution. Le nombre d’états parcourus ne sera donc plus égal au nombre de lettres du mot d’entrée mais pourra être beaucoup plus grand. L’arbre de calcul d’un automate avec transitions vides s’avère du coup être un outil moins intéressant que pour les automates non-déterministes sans transitions vides.

De l’automate avec transition vide aux mots reconnus

Le processus est le même que l’arbre créé par un automate non déterministe. Notons qu’en plus de devoir créer de nouvelles branches en cas d’indéterminisme, il faut aussi parcourir les transitions des états successeurs par epsilon-transition.

Si nous reprenons l’automate ci-dessus sur le mot aaaab :

p(aaaab) → q(aaab)→r(aaab)→s(aaab)→s(aab)→s(ab)→s(b)→q(b)→r – état terminal

Il est complexe de calculer les mots de longueur n reconnu par un automate avec epsilon transition, il faut alors faire la clôture de l’automate.

Le principe de l’algorithme consiste à remplacer chaque chemin de longueur 1 commençant par une epsilon-transition par une nouvelle transition qui décrit ce chemin.

Il y a deux chemin de longueur 1 qui commencent par la transition sur epsilon :

(1, ε, 3)(3, b, 3)
(1, ε, 3)(3, c, 4)

On ajoute à l’automate deux nouvelles transitions qui résument ces deux chemins :

(1, b, 3)
(1, c, 4)

Et on supprime la transition (1, ε, 3).

L’algorithme est un peu plus complexe dans les cas où plusieurs epsilon-transitions se suivent et si elles vont dans un état final, mais le principe général présenté ici reste valable (il suffit d’appliquer la première étape).