Chapitre 4 option informatique Corrigé des exercices • Automates finis détermini

Chapitre 4 option informatique Corrigé des exercices • Automates finis déterministes  
Exercice 1 1. Le langage des mots contenant au moins une fois la lettre a : q0 q1 a b a,b 2. Le langage des mots contenant au plus une fois la lettre a : q0 q1 a b b 3. Le langage des mots contenant un nombre pair de fois la lettre a : q0 q1 a b b a 4. Le langage des mots admettant aba pour facteur : q0 q1 q2 q3 a b a b a b a,b 5. Le langage des mots admettant aba pour sous-mot : q0 q1 q2 q3 a b a b a b a,b  
Exercice 2 Posons n = 2p + r avec r ∈{0,1} ; alors : p ≡0 mod 5 = ⇒n ≡r mod 5 p ≡3 mod 5 = ⇒n ≡1 + r mod 5 p ≡1 mod 5 = ⇒n ≡2 + r mod 5 p ≡4 mod 5 = ⇒n ≡3 + r mod 5 p ≡2 mod 5 = ⇒n ≡4 + r mod 5 D’où l’automate : http://info-llg.fr 4.2 option informatique q0 q1 q2 q3 q4 1 0 0 1 0 1 0 1 0 1 Pour lire les entiers à partir du bit de poids le plus faible, il suffit de considérer l’automate transposé, c’est-à-dire celui obtenu en inversant l’ordre des transitions et en échangeant états initiaux et états finaux. En général, la transposée d’un automate déterministe est non déterministe, mais l’automate ci-dessus fait exception. q0 q1 q2 q3 q4 1 0 0 1 0 1 0 1 0 1  
Exercice 3 Il y a trois types de mots dans ce langage : ceux qui contiennent au moins un a et un b avant le dernier caractère (état q6), ceux qui ne contiennent que des a et qui sont de longueur au moins 2 (état q3), ceux qui ne contiennent que des b et qui sont de longueur au moins 2 (état q5). q0 q1 q2 q3 q4 q5 q6 a b a b a b a b a,b a b a,b  
Exercice 4 1. Les mots de L′ sont les mots qui commencent par 1 et qui comportent au moins un 0 dans leur écriture. D’où l’automate : Corrigé des exercices 4.3 q0 q1 q2 1 1 0 0,1 2. Les mots de E sont reconnus par l’automate : q0 q1 q2 1 0 1 0 3. Notons L1 le langage dénoté par 01 et L2 le langage dénoté par (10)∗. Alors S = EL1L2 donc S est reconnu par l’automate : q0 q1 q2 q3 q4 1 0 1 0 1 1 0  
Exercice 5 On définit deux suites (Ri) et (Si) de parties de Q en posant R0 = {q0}, S0 = F et pour tout i ∈N : Ri+1 = Ri ∪ n q ∈Q il existe une transition d’un élément de Ri à q o Si+1 = Si ∪ n q ∈Q il existe une transition de q à un élément de Si o Ces deux suites sont croissantes dans Q fini donc sont stationnaires. Leurs limites R et S sont atteintes dès lors que deux termes consécutifs sont égaux et dans ce cas R est l’ensemble des états accessibles et S l’ensemble des états co-accessibles. Il suffit dès lors de supprimer les états qui n’appartiennent pas à R ∩S ainsi que les transitions dans lesquelles ces états interviennent pour obtenir l’automate émondé demandé. Commençons par une fonction qui détermine les états accessibles en suivant l’algorithme exposé ci-dessus : let accessible a = let rec aux1 b = function | [] −> b | ((i, _), j)::q when mem i b && not mem j b −> aux1 (j::b) q | _::q −> aux1 b q and aux2 b = let bb = aux1 b a.Delta in if b = bb then b else aux2 bb in aux2 [a.Start] ;; On détermine de même les états co-accessibles : http://info-llg.fr 4.4 option informatique let coaccessible a = let rec aux1 c = function | [] −> c | ((i, _), j)::q when mem j c && not mem i c −> aux1 (i::c) q | _::q −> aux1 c q and aux2 c = let cc = aux1 c a.Delta in if c = cc then c else aux2 cc in aux2 a.Accept ;; Il reste à émonder l’automate : let emonde a = let e = intersect (accessible a) (coaccessible a) in let rec aux = function | [] −> [] | ((i, _), j)::q when not mem i e || not mem j e −> aux q | t::q −> t::(aux q) in {Start = a.Start; Accept = intersect a.Accept e; Delta = aux a.Delta} ;; • Automates non déterministes  
Exercice 6 La déterminisation du premier automate conduit au résultat : δ′ a b {q0} {q0} {q0,q1} {q0,q1} {q0,q2} {q0,q1,q2} {q0,q2} {q0,q2} {q0,q1,q2} {q0,q1,q2} {q0,q2} {q0,q1,q2} q′ 0 q′ 1 q′ 2 q′ 3 a b a b a b b a La déterminisation du second automate conduit au résultat : δ′ a b {q0} {q1} {q2} {q1} {q1} {q0,q2} {q2} {q2} {q0} {q0,q2} {q1,q2} {q0,q2} {q1,q2} {q1,q2} {q0,q2} q′ 0 q′ 1 q′ 2 q′ 3 q′ 4 a b a b b a b a a b Corrigé des exercices 4.5  
Exercice 7 Seules quatre configurations sont possibles : – les quatre verres sont tous dans le même sens (configuration q0) ; – trois verres sont dans un sens et le quatrième dans l’autre sens (configuration q1) ; – deux verres voisins sont dans un sens et les deux autres dans l’autre sens (configuration q2) ; – deux verres opposés sont dans un sens et les deux autres dans l’autre sens (configuration q3). On désigne par la lettre : – a le fait de changer l’orientation d’un des quatre verres ; – b le fait de changer l’orientation de deux verres voisins ; – c le fait de changer l’orientation de deux verres opposés. Le jeu peut alors être représenté par l’automate non déterministe suivant : q0 q1 q2 q3 a a b a b c b,c c Sa déterminisation conduit à l’automate suivant : 0123 12 012 013 01 023 02 1 2 03 0 a,b c a c a c b a c a b,c b c a c b b,c a c a c b a b On constate que la succession de mouvement cbcacbc conduit nécessairement à une position gagnante pour le barman.  
Exercice 8 T (A) et donc A′ = D(T (A)) reconnait l’image miroir du langage reconnu par A, donc A′′ reconnait le même langage que A; il est équivalent à A. On obtient pour A′ l’automate : http://info-llg.fr 4.6 option informatique q′ 0 q′ 1 q′ 2 q′ 3 q′ 4 q′ 5 q′ 6 a b a b b a b b a b b a et pour A′′ l’automate : q′′ 0 q′′ 1 q′′ 2 a b a,b b a  
Exercice 9 L’automate non déterministe : q0 q1 q2 q3 q4 a,b a b b a a,b se déterminise en : δ′ a b {q0} {q0,q1} {q0} {q0,q1} {q0,q1} {q0,q2} {q0,q2} {q0,q1} {q0,q3} {q0,q3} {q0,q1,q4} {q0} {q0,q1,q4} {q0,q1,q4} {q0,q4} {q0,q4} {q0,q1,q4} {q0,q4} q′ 0 q′ 1 q′ 2 q′ 3 q′ 4 q′ 5 b a a b a b a b a b a b On notera que l’état q′ 5 peut être supprimé sans changer le langage reconnu par cet automate. L’algorithme KMP consiste à considérer les états et transitions suivants : δ a b ε a ε a a ab ab a abb abb abba ε abba a ab Corrigé des exercices 4.7 puis à transformer l’état acceptant (abba) en puit : ε a ab abb abba b a a b a b a b a,b • Théorème de Kleene  
Exercice 10 On commence par se débarrasser du symbole ε : l’expression rationnelle est équivalente à (a+c)∗abb+(a+c)∗. On la linéarise pour obtenir un langage local : (c1+c2)∗c3c4c5+(c6+c7)∗, avec P = {c1,c2,c3,c6,c7}, S = {c5,c6,c7} et F = {c2 1,c2 2,c1c2,c2c1,c1c3,c2c3,c3c4,c4c5,c2 6,c2 7,c6c7,c7c6}. On déduit de l’automate local qui en résulte l’automate de Glushkov de l’expression rationnelle en supprimant le marquage des transitions : c0 c3 c4 c5 c2 c1 c6 c7 a c a a c c a a a a c b b c a a c On notera que puisque ε appartient au langage c0 est un état acceptant. Sa déterminisation fournit l’automate suivant : q0 q1 q2 q3 q4 a c a c b c a b  
Exercice 11 L’automate suivant reconnait le langage L = n m ∈Σ∗ |m|a ≡0 mod 3 o : http://info-llg.fr 4.8 option informatique q0 q1 q2 a b a b a b On lui applique l’algorithme d’élimination des états uploads/Religion/ 04-corrige.pdf

Documents similaires

Ecole nationale supérieure d'informatique 1CPI - Semestre 2 Mécanique du point 0 0

Analyse Combinatoire Probabilité Page 1 sur 7 Adama Traoré Professeur Lycée Tec 0 0

Les exercices pratiques de sophrologie Le déroulement sophrologique T outes les 0 0

Ecole nationale supérieure d'informatique 1CPI - Semestre 2 Mécanique du point 0 0

Formation de d´ eveloppements limit´ es ´ Enonc´ es ´ Enonc´ es des exercices E 0 0

HP16 SÉQUENCE 5 SÉANCE 5 Course contents Table des matières 1 SÉANCE 5 - UNE IN 0 0

Groupe Scolaire Année Scolaire 2008 – 2009 du Collège Saint Joseph Lundi 17 Nov 0 0

Statistique et probabilités Cours et exercices corrigés Jean-Pierre Lecoutre Ma 0 0

LANGAGE C J’APPRENDS À ECRIRE DES PROGRAMMES EN LANGAGE C NO EXPIRATION DATE E 0 0

HP16 SÉQUENCE 5 SÉANCE 5 Course contents Table des matières 1 SÉANCE 5 - UNE IN 0 0

• Détails
• Publié le Jul 17, 2022
• Catégorie Religion
• Langue French
• Taille du fichier 0.1822MB