Remerciez-le!

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

Grapes1td2 2 IUT Info A Ann ?ee - P ?eriode Graphes et Automates Feuille de TD n B Gugger F Madelaine C Simon D Richard Les polycopi ?es du cours les feuilles de TD et quelques corrig ?es sont disponibles a l ? url suivante http laic u-clermont fr fmadela

IUT Info A Ann ?ee - P ?eriode Graphes et Automates Feuille de TD n B Gugger F Madelaine C Simon D Richard Les polycopi ?es du cours les feuilles de TD et quelques corrig ?es sont disponibles a l ? url suivante http laic u-clermont fr fmadelaine teaching graphe html D ?eterminisation L ? id ?ee On va simuler en m eme temps plusieurs ?etats d ? un automate non-d ?eterministe Concretement on considere maintenant des super- ?etats qui sont des ensemble d ? ?etats On utilise alors la m ?ethode suivante ?? Un super- ?etat qui ne contient que des ?etats initiaux est initial ?? Un super- ?etat qui contient un ?etat ?nal est ?nal et ?? Un super ?etat S transite en lisant une lettre a vers le super- ?etat S qui est l ? union pour tout ?etat s de S de l ? ensemble de tous les ?etats s tels que s transite vers s en lisant la lettre a Mise en oeuvre On d ?eterminise l ? automate suivant senter la fonction de transition de l ? automate d ?eterministe remarque super- ?etat a b initial ? ?nal C ? est-a -dire l ? automate d ?eterministe suivant Comme les supers- ?etats qui ne sont pas accessibles depuis les super- ?etats initiaux ne servent a rien on ne calcule que ceux qui sont accessibles On utilise un tableau pour repr ?e- Exercice Construire un automate ?ni d ?eterministe ?equivalenta l ? automate suivant D ?eterminiser verbe rendre d ?eterministe Ne pas confondre avec D ?eterminer verbe calculer Cfeuille de TD n Graphe et Automates Combiner des automates On dispose de l ? automate A qui reconna t le langage L et de A qui reconna t L On cherche a construire a partir de A et de A l ? automate pour les langages L L L L et L ?? L Concat ?enation Somme union On construit l ? automate pour le langage On construit l ? automate pour le langage L L L L w w tel que w ?? L et w ?? L L L L L w tel que w ?? L ou w ?? L On a ajout ?e des arcs entre les ?etats ?naux de M qui ne sont plus ?naux dans le nouvel automate et les ?etats initiaux de M Ces arcs sont des transitions particuli eres qui ne lisent aucune lettre autrement dit le mot vide On parle alors de -transition Produit intersection On construit l ? automate pour le langage L L ?? L w tel que w ?? L et w ?? L On a des ?etats doubles l ? ?etat h correspond simultan ?ement a l ? ?etat h de A eta l ? ?etat de A Le nouvel automate simule de mani ere synchronis ?ee les transitions de A et A Cfeuille de TD n Graphe et Automates Exercice Soit A l ? automate dessin ?e a gauche et A celuis