Quelques catégories particulières d’AFD

15.4.1 AFD complets

Définition (AFD complets) On dit qu’un automate fini déterministe {\mathcal{A}} est complet si sa fonction de transition ne connaît aucun blocage.

  • cela équivaut à dire que la fonction de transition {\delta} est définie sur {Q\times \Sigma} tout entier (et à valeurs dans {Q)} {\star}
  • dans un AFD complet, la suite des transitions associées à un mot quelconque de {\Sigma} ne connaît aucun blocage : {\forall q\in Q,\forall m\in \Sigma^{\star},\exists q^{\prime }\in Q,\delta (q,m)=q^{\prime }}
  • on peut toujours transformer un AFD {\mathcal{A}} non complet en un AFD complet équivalent : il suffit pour cela d’ajouter un état supplémentaire {q_{\infty }} vers lequel on dirige toutes les transitions qui provoquent un blocage dans {\mathcal{A}.}
Figure du chapitre 15, page 4

L’automate ci-dessus n’est pas complet car la transition {\delta (q_{0},b)} provoque un blocage.

L’automate ci-dessous, équivalent au précédent, a été rendu complet en créant un état supplémentaire {q_{\infty }} non final et sur lequel on dirige (définitivement !) la transition manquante {\delta (q_{0},b).} On exprime cette situation en disant que {q_{\infty }} est un « puits ».

Figure du chapitre 15, page 4

La fonction trans_abs renvoie la liste des transitions absentes dans un AFD {\mathcal{A}.}

  • Elle appelle les fonctions déjà définies etats_afd (liste des états de {\mathcal{A})} et alph_afd (liste des lettres de {\mathcal{A}).}
  • Elle utilise aussi la fonction intégrée List.mem_assoc (qui teste si un élément {x} est la première composante d’au moins un couple dans une liste de couples).

Voici un AFD qui possède les deux transitions manquantes {\delta (q_{0},b)} et {\delta (q_{2},a):}

La fonction suivante prend un AFD en argument et le complète « en place » (s’il est déjà complet rien ne se passe), en ajoutant un état « puits » nommé {\infty (}toutes les transitions manquantes {\delta (q,a)} deviennent {\delta (q,a)=\infty ,} et on ajoute des transitions {\delta (\infty ,a)=\infty} pour toutes les lettes de l’AFD) :

On reprend l’exemple précédent d’un AFD non complet, on le complète, et on voit le résultat :

Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :