Next PDF List

Théorie des Langages FormelsChapitre 4 : Automates complets déterministesFlorence LevéFlorence.Leve@u-picardie.frAnnée 2017-20181/23Introduction123456789101112aaaababaabaababababaaabbRecherche de :abaab,ababba2/23Automate déterministeAutomate déterministe.Un automate est déterministe si etseulement si les deux conditions suivantes sont vérifiées :1.L"a utomatep ossèdeun et un seul état initial ;2.P ourchaque ét atqet pour chaque lettre, il existeau plus une transition issue deqd"étiquette.Quand un automate est déterministe, l"ensemble destransitions est souvent vu comme une fonction deQAdansQ.

L"ensemble des transitions est alors présenté sous formed"un tableau à deux dimensions.

On note alors(q;a)l"étatq0(s"il existe) tel que(q;a;q0)est une transition.3/23Exemples123aba123aab123aab4/23Exemples123aba123aab123aab4/23Exemples123aba123aab123aab4/23Exemples123aba123aab123aabLe troisième automate est déterministe, mais pas complet.4/23Automate completDéfinition.Un automate est complet si pour chaque étatqetpour chaque lettre, il existe au moins une transition issue deqétiquetée par.Etat puits.Pour un automate complet, on appelleétat puits,tout étatenon terminal tel que pour toute transition(e;;f),e=f.Algorithme de complétion.Pour rendre un automatecomplet :IAjouter un état puitsP;IAjouter pour chaque étatq, et chaque lettre, une transition(q;;P)s"il n"existe pas déjà une transition partant deqparla lettre.IPour chaque lettre, ajouter la transition(P;;P).Remarque : La complétion ne change ni le langage reconnu, nile déterminisme éventuel de l"automate.5/23Exemple123aab6/23Exemple123aabP6/23Exemple123aabbPa,b6/23Exemple123aabbPa,ba,b6/23Exemple123aabbPa,ba,bAttention : P n"est pas un état d"acceptation!!6/23Exemple123aabbPa,ba,bAttention : P n"est pas un état d"acceptation!!Remarque : un automate peut être non déterministe maiscomplet.6/23Déterminisation (méthode des sous-ensembles)Pour tout automate finiAut=, l"automateAutdsuivant est déterministe complet et reconnaît le mêmelangage queAut:Autd=oùIQd=2Qi.e. les états deAutdsont les parties (sous-ensembles) deQ;IDd=fDgi.e.Ddne contient qu"un état qui est l"ensemble des étatsinitiaux deAut;IFd=fP2QdjP\F6=;gi.e. est état d"acceptation toute partie deQqui contient aumoins un état d"acceptation deAut;Id=f(P;;P0)jP;P02Qd;2Atels queP0=fq0j(q;;q0)2;q2Pggi.e. l"unique transition dansAutdqui part deP2Qdétiquetée par la lettremène dans l"ensembleP0qui estl"ensemble des états deAutqu"on peut atteindre par unetransition étiquetée paren partant d"un état deP.7/23Pourquoi ça marche?On vérifie aisément que l"automate construit est déterministeet complet.Propriété: siPetP0sont deux ensembles d"états deQ(deuxétats deQd), il existe un chemin partant dePaboutissant enP0étiqueté par un motusi et seulement s"il existe un étatpdansP, un étatp0dansP0tels qu"il existe un chemin dansAutpartant deparrivant dansp0d"étiquetteu.Se démontre par récurrence suru.D"où l"égalité des langages.Remarque : l"automate construit n"est en général pas émondé.8/23Construction de la table de transitionsDonnée: un automateAut=Résultat: la table de transitions de l"automate accessible deAutd.1.Définir un tableau à deux dimensions a yantune colonne de plus que de lettres dans l"alphabet.2.Étiqueter la p remièrecolonne "états" (les valeurs dans cette colonne qui seront les états de l"automate déterministe,étiquetteront les lignes).3.Étiqueter les autres colonnes pa rles lettres de l"alphab et.4.Placer sur une p remièreligne en p remièrecolonne, l"ensemble des états de départ deAut.5.T antqu"au moins une case du tableau n"est pas remplie : Ichoisir une case à remplir : notonsPl"ensemble d"états deAutfigurant en première colonne de la ligne de cette case, etnotonsla lettre étiquetant la colonne de la case;Icalculer la valeur de la case :(P;);Isi aucune ligne n"est associée à cette valeur, commencer unenouvelle ligne étiquetée par cette valeur.9/23Calcul de l"automate déterministe completDonnée: un automateAut=,Résultat: construit l"automate accessibleAut0de l"automateAutd.Émonder l"automateAut.Appliquer l"algorithme précédent de construction de la table detransitions.Ià la fin de cet algorithme, sont connus l"alphabet deAut0(c"estA), les états deAut0(ce sont les états qui apparaissentdans la première colonne de la table), les transitions deAut0(elles se lisent dans la table).Marquer l"état initial deAut0: il s"agit de l"état sur la premièreligne de la table; le marquer visuellement par une flèche!juste devant l"état de la table.Déterminer et marquer les états terminaux deAut0: pour lemarquage mettre une flèche devant chaque état concerné(si l"état initial est aussi terminal, on pourra remplacer laflèche!par une flèche$)10/23Exemple123baabaL"automate est émondé.11/23Exemple : calcul de la table de transition123baaba12/23Exemple : calcul de la table de transition123baaba1.

Définir un tableau à deux dimensions ayant une colonne de plusque de lettres dans l"alphabet.12/23Exemple : calcul de la table de transition123baaba2. Étiqueter la première colonne "états".états12/23Exemple : calcul de la table de transition123baaba3. Étiqueter les autres colonnes par les lettres de l"alphabet.étatsab12/23Exemple : calcul de la tabl