Automate avec transition vide

On a l’habitude de dessiner les automates, 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 déterministe A avec epsilon transition (ou 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 transitions 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.

 

Publicités