Remerciez-le!

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

IUT Info 1A Ann´ ee 2007-08 P´ eriode 1 Graphes et Automates B. Gugger F. Madel

IUT Info 1A Ann´ ee 2007-08 P´ eriode 1 Graphes et Automates B. Gugger F. Madelaine C. Simon D. Richard Feuille de TD n◦2 Les polycopi´ es du cours, les feuilles de TD et quelques corrig´ es sont disponibles ` a l’url suivante. http ://laic.u-clermont1.fr/~fmadelaine/teaching/graphe1.html 1 D´ eterminisation L’id´ ee On va simuler en mˆ eme temps plusieurs ´ etats d’un automate non-d´ eterministe. Concr` etement, on consid` ere 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´ eterminise1 l’automate suivant. Comme les supers-´ etats qui ne sont pas ac- cessibles depuis les super-´ etats initiaux ne servent ` a rien, on ne calcule que ceux qui sont accessibles. On utilise un tableau pour repr´ e- senter la fonction de transition de l’automate d´ eterministe. remarque super-´ etat a b initial {0} {1} ∅ {1} {1} {1, 2} ﬁnal {1, 2} {1} {1, 2} C’est-` a-dire l’automate d´ eterministe suivant. Exercice 1. Construire un automate ﬁni d´ eterministe ´ equivalent ` a l’automate suivant. 1D´ eterminiser : (verbe) rendre d´ eterministe. Ne pas confondre avec D´ eterminer : (verbe) calculer. 1 feuille de TD n◦2 Graphe et Automates 2 Combiner des automates On dispose de l’automate A1 qui reconnaˆ ıt le langage L1 et de A2 qui reconnaˆ ıt L2. On cherche ` a construire ` a partir de A1 et de A2 l’automate pour les langages L1L2, L1 + L2 et L1 ∩L2. Concat´ enation On construit l’automate pour le langage L = L1L2 L = {w1w2 tel que w1 ∈L1 et w2 ∈L2}. On a ajout´ e des arcs entre les ´ etats ﬁnaux de M1 (qui ne sont plus ﬁnaux dans le nouvel au- tomate) et les ´ etats initiaux de M2. Ces arcs sont des transitions particuli` eres, qui ne lisent aucune lettre, autrement dit le mot vide ε. On parle alors de ε-transition. Somme (union) On construit l’automate pour le langage L = L1 + L2 L = {w tel que w ∈L1 ou w ∈L2}. Produit (intersection) On construit l’automate pour le langage L = L1 ∩L2 = {w tel que w ∈L1 et w ∈L2}. On a des ´ etats doubles : l’´ etat (h, 6) correspond simultan´ ement ` a l’´ etat h de A1 et ` a l’´ etat 6 de A2. Le nouvel automate simule de mani` ere synchronis´ ee les transitions de A1 et A2. 2 feuille de TD n◦2 Graphe et Automates Exercice 2. Soit A1 l’automate dessin´ e ` a gauche et A2 celuis de droite. Soient L1 et L2 leurs langage respectifs. a - Construire l’automate de L1L2. b - Mˆ eme question mais sans ε-transition. c - Construire l’automate de L1 + L2 d - Construire l’automate de (L1)⋆L2 e - Construire l’automate de L1 ∩L2 3 Des automates aux langages Le lemme d’Arden Ce r´ esultat dit que l’´ equation r´ ecursive suivante X = LX + M o` u X est le langage cherch´ e et L et M sont deux langages connus, a une unique solution qui est : X = L⋆M. Attention : ici, on suppose que L ne contient pas le mot vide. M´ ethode du syst` eme des d´ eparts On cherche ` a d´ eterminer le langage de l’auto- mate suivant. On s’int´ eresse au langage L1 des mots qui passent par l’´ etat 1, et ` a L2 celui des mots qui passent par 2. On a les ´ equations suivantes. ( L1 = ε+aL1 + bL2 L2 = aL1 + bL2 Ici ε apparaˆ ıt puisque l’´ etat 1 est initial. Par le lemme d’Arden sur la seconde ´ equa- tion, il vient L2 = b⋆(aL1). En r´ ecrivant la premi` ere, on a L1 = ε + aL1 + b(b⋆aL1) = ε + aL1 + b+aL1 = b⋆aL1 + ε Par le lemme d’Arden sur cette ´ equation, on obtient ﬁnalement que : L1 = (b⋆a)⋆ε = (b⋆a)⋆. 3 feuille de TD n◦2 Graphe et Automates Exercice 3. D´ eterminer le langage reconnu par l’automate suivant. Exercice 4. On consid` ere le syst` eme d’´ equations suivant :    L1 = aL1 + bL2 + cL3 L2 = cL2 + bL1 + aL3 L3 = c + aL2 + bL3 Trouver l’expression rationnelle de L1. Exercice 5. D´ eterminer le langage reconnu par l’automate de l’exercice 1. Exercice 6. a - Donner l’expression rationnelle du langage reconnu par l’automate ci-dessous. b - D´ eterminiser cet automate. Exercice 7. Soit le langage sur l’alphabet Σ = {a, b} constitu´ e des mots dont la derni` ere lettre apparaˆ ıt au moins une fois dans la partie initiale (i.e. dans le mot priv´ e de sa derni` ere lettre). a - Trouver un automate A non d´ eterministe reconnaissant L. b - Trouver un automate A non d´ eterministe ` a 4 ´ etats reconnaissant L. c - D´ eterminiser l’automate A. d - Trouver une expression rationnelle d´ esignant L. Exercice 8. On consid` ere l’alphabet Σ = {a, b, c}. a - Construire un automate d´ eterministe qui reconnaˆ ıt le langage a∗ba + a+b∗c. b - Mˆ eme question pour (a∗ba + a+b∗c)∗. c - Mˆ eme question pour ca + c∗b. d - Mˆ eme question pour (a∗ba + a+b∗c)∗(ca + c∗b) Exercice 9. Donner un automate d´ eterministe qui reconnaˆ ıt les mots sur {a, b} ne contenant ni le facteur a2 ni le facteur b3 et qui sont de taille multiple de 3. En donner l’expression rationnelle. 4 uploads/s3/ grapes1td2-2.pdf