Automate complet

Dans la définition de base d’un automate fini, il n’est pas nécessaire que, depuis tous les états, il existe une transition pour tous les symboles. Un automate complet est un automate qui a des transitions définies depuis tous les états pour tous les symboles de l’alphabet d’entrée.

Comment construire un automate complet

Prenons cet automate A = (Q ; Σ ; δ ; q₀ ; F) :

Ici, la transition depuis l’état q₀ pour la lettre « b » n’est pas dessinée. Si une telle situation se produit, nous disons que l’automate n’accepte pas le mot d’entrée. Cependant, du point de vue de la formalisation, il peut être gênant que la fonction de transition δ ne soit pas définie pour certaines valeurs ; ici, par exemple, elle n’est pas définie pour δ(q₀, b).

On résout facilement le problème en construisant un automate équivalent qui a un état de plus : les transitions « manquantes » iront vers cet état, il ne sera pas final et toutes les lectures suivantes boucleront sur cet état. Nous appelons cet automate automate complet. L’automate équivalent modifié pourrait ressembler à ceci :

Nous avons ajouté l’état q_fail. Depuis les autres états, nous avons tracé une transition vers lui si et seulement s’il n’y en avait pas auparavant. Cet état n’est pas final et il boucle pour toutes les entrées suivantes. Si, dans l’automate précédent, nous tombions sur une transition manquante, ici il n’y a aucune transition manquante et l’automate arriverait dans l’état q_fail.

Nous pouvons donc toujours supposer, sans perte de généralité, que l’automate a des transitions définies pour toutes les combinaisons d’états et de lettres de l’alphabet.

Définition

Pour un automate complet A = (Q ; Σ ; δ ; q₀ ; F), on a donc

$$\mathrm{\forall }q\in Q\mathrm{\forall }a\in \mathrm{\Sigma }\mathrm{\exists }r\in Q:\delta (q,a)=r.$$

Sources

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools