Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Determiniser un afn Déterminisation d'un AFN ou d'un AFN a b a b C Suppression des transitions a Calcul des clôtures Cl Cl Cl Cl C Suppression des transitions a Calcul des clôtures b Calcul des transitions étendues Q ? a b x Cl C Suppression des transitio

Déterminisation d'un AFN ou d'un AFN a b a b C Suppression des transitions a Calcul des clôtures Cl Cl Cl Cl C Suppression des transitions a Calcul des clôtures b Calcul des transitions étendues Q ? a b x Cl C Suppression des transitions a Calcul des clôtures b Calcul des transitions étendues Q ? a b x Cl Cl C Suppression des transitions a Calcul des clôtures b Calcul des transitions étendues Q ? a b x Cl Cl Cl C Suppression des transitions a Calcul des clôtures b Calcul des transitions étendues Q ? a b x Cl Cl Cl Cl C Suppression des transitions a Calcul des clôtures b Calcul des transitions étendues c États acceptants Q ? a b x Cl Cl Cl Cl hérite du caractère acceptant de qui est dans sa clôture C Suppression des transitions Q ? a b x non accessible peut être émondé C Suppression des transitions Q ? a b x On renomme l'état COn obtient ?nalement un automate non déterministe Q ? a b x a b b a Mais qui n'a plus de a b transition spontanées COn peut à son tour le déterminiser a b b a a b COn peut à son tour le déterminiser Q ? a b I II x COn peut à son tour le déterminiser Q ? I II a II II b x III COn peut à son tour le déterminiser Q ? I II III a II II II b x III III COn peut à son tour le déterminiser Q ? I II III a II II II b x III III CD'o? ?nalement l'AFD équivalent a b a a b COn remarque que et constituent un piège acceptant qui peut fusionner en un unique état D'o? l'automate équivalent ?nal b a a CComparons la lecture du mot abba ? par les trois automates Par l'automate initial l'arbre de lecture conduisant à une lecture acceptante est le suivant CPar l'automate initial l'arbre de lecture conduisant à une lecture acceptante est le suivant b b a a b b a b a b CAvec l'automate non déterministe mais sans transition spontanée l'arbre de lecture est a b a b b a b a b CAvec l'automate déterministe on a une simple cha? ne de lecture a b b a La résolution du problème de décision est donc beaucoup plus e ?cace C