Remerciez-le!

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

Aut chapitre 3 CHAPITRE AUTOMATES FINIS NON-DETERMINISTES AFN Dé ?nition des automates ?nis non-déterministes AFN Dé ?nition générale Dé ?nition Un automate ?ni non-déterministe AFN sur un alphabet ? est la donnée d ? un n-uplet Q ? I F o? ? Q est un ense

CHAPITRE AUTOMATES FINIS NON-DETERMINISTES AFN Dé ?nition des automates ?nis non-déterministes AFN Dé ?nition générale Dé ?nition Un automate ?ni non-déterministe AFN sur un alphabet ? est la donnée d ? un n-uplet Q ? I F o? ? Q est un ensemble ?ni d ? états ? ? est une fonction de transition de Q ? ? dans P Q ensemble des parties de Q ? I est une partie de Q d ? états dits initiaux ? F est une partie de Q d ? états dits ?nals Fonctionnement Un automate ?ni non-déterministe est un automate tel que dans un état donné il peut y avoir plusieurs transitions avec la même lettre Au temps initial la machine est dans un état initial i ?? I Si à l ? instant t la machine est dans l ? état q et lit a alors à l ? instant t ? si ? q a ? la machine se bloque si ? q a ?? ? la machine se met dans l ? un des états ?? ? q a et lit le symbole suivant On voit que le fonctionnement n ? est pas complètement déterminé ? car on ne sait pas à l ? avance quel état la machine doit choisir dans ? q a d ? o? le terme non-déterministe On pourrait donc penser que les AFN n ? ont aucun intérêt dans la pratique En fait il n ? en est rien car on peut montrer que tout AFN peut être remplacé par un AFD équivalent voir algorithme de déterminisation Donc on se sert des AFN car ils peuvent être très utiles pour exprimer certains problèmes et on les remplace ensuite par des AFD Exemple ensemble des mots qui se terminent par ab Q I F ? dé ?nie par la table de transition C a ? ? b ? Langage reconnu par un AFN Un mot u est accepté par un AFN s ? il existe un chemin d ? étiquette u partant de l ? un des états initiaux et arrivant à l ? un des états ?nals Dé ?nition Le langage reconnu ou accepté par un automate AFN est l ? ensemble des mots acceptés par l ? AFN c ? est-à-dire qui correspondent à un calcul de l ? automate partant d ? un état initial et s ? arrêtant dans un état ?nal Déterminisation d ? un AFN Algorithme de déterminisation d ? un AFN Un AFD est un cas particulier d ? AFN avec Card ? q a ? pour tous q ?? Q a ?? ? Donc tout langage reconnu par un AFD est reconnu par un AFN Plus surprenant on a la réciproque Théorème Rabin-Scott Tout langage reconnu par un AFN peut être reconnu par un AFD Le principe de la construction est de prendre comme états de l ? AFD les ensembles d ? états de l ? AFN L ? unique état initial de l ? AFD