Remerciez-le!

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

a b b 1 ε 3 4 2 Déterminisation d'un AFN ou d'un AFNε ε a 1) Suppression des ε

a b b 1 ε 3 4 2 Déterminisation d'un AFN ou d'un AFNε ε a 1) Suppression des ε transitions a) Calcul des clôtures : ● Cl(1) = {1} ● Cl(2) = {2,3,4} ● Cl(3) = {3,4} ● Cl(4) = {4} 1) Suppression des ε transitions a) Calcul des clôtures : b) Calcul des transitions étendues Q \ Σ a b 1 2 x 2 3 4 Cl(1) = {1} 1) Suppression des ε transitions a) Calcul des clôtures : b) Calcul des transitions étendues Q \ Σ a b 1 2 x 2 2 2,4 3 4 Cl(1) = {1} Cl(2) = {2,3,4} 1) Suppression des ε transitions a) Calcul des clôtures : b) Calcul des transitions étendues Q \ Σ a b 1 2 x 2 2 2,4 3 2 2,4 4 Cl(1) = {1} Cl(2) = {2,3,4} Cl(3) = {3,4} 1) Suppression des ε transitions a) Calcul des clôtures : b) Calcul des transitions étendues Q \ Σ a b 1 2 x 2 2 2,4 3 2 2,4 4 2 4 Cl(1) = {1} Cl(2) = {2,3,4} Cl(3) = {3,4} Cl(4) = {4} 1) Suppression des ε transitions a) Calcul des clôtures : b) Calcul des transitions étendues c) États acceptants Q \ Σ a b 1 2 x 2 2 2,4 3 2 2,4 4 2 4 Cl(1) = {1} Cl(2) = {2,3,4} Cl(3) = {3,4} Cl(4) = {4} 2 hérite du caractère acceptant de 3 qui est dans sa clôture 1) Suppression des ε transitions 3, non accessible, peut être émondé. Q \ Σ a b 1 2 x 2 2 2,4 3 2 2,4 4 2 4 Q \ Σ a b 1 2 x 2 2 2,3 3 2 3 1) Suppression des ε transitions On renomme l'état 4 Q \ Σ a b 1 2 x 2 2 2,3 3 2 3 On obtient finalement un automate non déterministe : a b b 1 2 3 a a b Mais qui n'a plus de transition spontanées On peut à son tour le déterminiser : a b b 1 2 3 a a b On peut à son tour le déterminiser : Q \ Σ a b I = {1} II = {2} x On peut à son tour le déterminiser : Q \ Σ a b I = {1} II = {2} x II = {2} II III = {2,3} On peut à son tour le déterminiser : Q \ Σ a b I = {1} II = {2} x II = {2} II III = {2,3} III = {2,3} II III On peut à son tour le déterminiser : Q \ Σ a b I = {1} II = {2} x II = {2} II III = {2,3} III = {2,3} II III D'où finalement l'AFD équivalent : a b b 1 3 a a 2 On remarque que 2 et 3 constituent un piège acceptant qui peut fusionner en un unique état. D'où l'automate équivalent final : a b 1 a 2 Comparons la lecture du mot « abba » par les trois automates : Par l'automate initial, l'arbre de lecture conduisant à une lecture acceptante est le suivant : Par l'automate initial, l'arbre de lecture conduisant à une lecture acceptante est le suivant : a 1 2 3 2 4 ε b b 4 b ε 4 b 2 a 3 ε ε 3 2 4 b ε ε 3 4 ε 2 a 3 ε 2 a 3 ε 4 b Avec l'automate non déterministe, mais sans transition spontanée, l'arbre de lecture est : a 1 3 2 b b a 2 3 2 b b 3 b 2 a 2 a 2 Avec l'automate déterministe, on a une simple chaîne de lecture : a 1 2 a 2 2 2 b b La résolution du problème de décision est donc beaucoup plus efficace ! uploads/s1/ determiniser-un-afn.pdf