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}.}

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 ».

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})} etalph_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).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
let trans_abs afd = (* former la liste des transitions absentes dans un AFD *) let ltm = ref [] (* deviendra le liste des transitions manquantes *) and etats = etats_afd afd (* la liste des états de l'AFD *) and lettres = alph_afd afd (* la liste des lettres de l'AFD *) in let rec aux le ll = (* le = liste états restants; ll = liste de lettres *) match le, ll with | [], _ -> () (* plus d'états à visiter *) | q :: r, [] -> aux r lettres (* plus de lettres => passer aux états suivants *) | q :: r, a :: s -> (* un état q et une lettre a *) if not (List.mem_assoc (q,a) afd.trans) (* si la transition delta(q,a) est absente *) then ltm := (q,a) :: !ltm; (* alors on l'ajoute à la liste ltm *) aux le s (* passe à la lettre suivante *) in aux etats lettres; (* cherche la liste des transitions manquantes *) !ltm;; (* renvoie cette liste des transitions manquantes *) val trans_abs : automate_fd -> (string * string) list = <fun> |
Voici un AFD qui possède les deux transitions manquantes {\delta (q_{0},b)} et {\delta (q_{2},a):}
|
1 2 3 4 5 6 |
let mon_afd = { initial = "q0"; final = ["q0"; "q2"] ; trans = [ ("q0", "a"), "q1"; ("q1", "a"), "q2"; ("q1", "b"), "q1"; ("q2", "b"), "q2" ]} ;; trans_abs mon_afd;; - : (string * string) list = [("q2", "a"); ("q0", "b")] |
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) :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
let complete_afd afd = let ltm = trans_abs afd (* listes des transitions absentes *) and alph = alph_afd afd in (* alphabet de l'automate *) if ltm <> [] then (* si déjà complet, ne rien faire *) let rec aux1 l = match l with (* remplacer toute transition manquante ... *) | [] -> () (* ... delta(q,a) par delta(q,a) = inf *) | (q, a) :: r -> afd.trans <- ((q,a),"∞") :: afd.trans; aux1 r; and aux2 l = match l with (* ajouter des transitions du puits "inf" ... *) | [] -> () (* vers chacune des lettres de l'automate *) | a :: r -> afd.trans <- (("∞",a),"∞") :: afd.trans; aux2 r; in aux1 ltm; aux2 alph;; (* ajoute les transitions vers et depuis inf *) val complete_afd : automate_fd -> unit = <fun> |
On reprend l’exemple précédent d’un AFD non complet, on le complète, et on voit le résultat :
|
1 2 3 4 5 6 7 8 9 10 |
let mon_afd = { initial = "q0"; final = ["q0"; "q2"] ; trans = [ ("q0", "a"), "q1"; ("q1", "a"), "q2"; ("q1", "b"), "q1"; ("q2", "b"), "q2" ]} ;; complete_afd mon_afd;; - : unit = () mon_afd;; - : automate_fd = { initial = "q0"; final = ["q0"; "q2"]; trans = [ (("∞", "b"), "∞"); (("∞", "a"), "∞"); (("q0", "b"), "∞"); (("q2", "a"), "∞"); (("q0", "a"), "q1"); (("q1", "a"), "q2"); (("q1", "b"), "q1"); (("q2", "b"), "q2") ]} |
- avoir une souscription active sur mathprepa
- et être connecté au site
- revenir à la page d'accueil
- ou tester la page d'extraits libres