Next PDF List

Chapitre 4option informatiqueCorrigé des exercicesAutomates finis déterministesExercice 11.Le lang agedes mots con tenanta umoins une f oisla lettre a:q0q1aba;b2.Le lang agedes mots con tenanta upl usune f oisla lettre a:q0q1abb3.Le lang agedes mots con tenantun nombre pair de f oisla lettre a:q0q1abba4.Le lang agedes mots admettan tabapour facteur :q0q1q2q3abababa;b5.Le lang agedes mots admettan tabapour sous-mot :q0q1q2q3abababa;bExercice 2Posonsn= 2p+ravecr2 f0;1g; alors :p0 mod 5 =)nrmod 5p3 mod 5 =)n1+rmod 5p1 mod 5 =)n2+rmod 5p4 mod 5 =)n3+rmod 5p2 mod 5 =)n4+rmod 5D"où l"automate :http://info-llg.fr4.2option informatiqueq0q1q2q3q41001010101Pour lire les entiers à partir du bit de poids le plus faible, il suffit de considérer l"automate transposé, c"est-à-direcelui obtenu en inversant l"ordre des transitions et en échangeant états initiaux et états finaux.

En général, latransposée d"un automate déterministe est non déterministe, mais l"automate ci-dessus fait exception.q0q1q2q3q41001010101Exercice 3Il y a trois types de mots dans ce langage : ceux qui contiennent au moins unaet unbavant ledernier caractère (étatq6), ceux qui ne contiennent que desaet qui sont de longueur au moins 2 (étatq3), ceuxqui ne contiennent que desbet qui sont de longueur au moins 2 (étatq5).q0q1q2q3q4q5q6ababababa;baba;bExercice 41.Les mots deL0sont les mots qui commencent par 1 et qui comportent au moins un 0 dans leur écriture.D"où l"automate :Corrigé des exercices4.3q0q1q21100;12.Les mots de E son treconn uspar l" automate: q0q1q210103.NotonsL1le langage dénoté par01etL2le langage dénoté par(10).

AlorsS=EL1L2doncSest reconnupar l"automate :q0q1q2q3q41010110Exercice 5On définit deux suites (Ri) et (Si) de parties de Q en posant R0=fq0g, S0= F et pour touti2N:Ri+1= Ri[nq2Qil existe une transition d"un élément de RiàqoSi+1= Si[nq2Qil existe une transition deqà un élément de SioCes deux suites sont croissantes dansQfini donc sont stationnaires.

Leurs limitesRetSsont atteintes dès lorsque deux termes consécutifs sont égaux et dans ce casRest l"ensemble des états accessibles etSl"ensembledes états co-accessibles.

Il suffit dès lors de supprimer les états qui n"appartiennent pas àR\Sainsi que lestransitions 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 :letaccessible a =letrec aux1 b =function| []> b| ((i, _), j)::q when mem i b &¬mem j b> aux1 (j::b) q| _::q> aux1 b qandaux2 b =letbb = aux1 b a.Deltainifb = bbthenbelseaux2 bbinaux2 [a.Start] ;;On détermine de même les états co-accessibles :http://info-llg.fr4.4option informatiqueletcoaccessible a =letrec aux1 c =function| []> c| ((i, _), j)::q when mem j c &¬mem i c> aux1 (i::c) q| _::q> aux1 c qandaux2 c =letcc = aux1 c a.Deltainifc = ccthencelseaux2 ccinaux2 a.Accept ;;Il reste à émonder l"automate :letemonde a =lete = intersect (accessible a) (coaccessible a)inletrec aux =function| []> []| ((i, _), j)::q whennotmem i e ||notmem 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éterministesExercice 6La déterminisation du premier automate conduit au résultat :0a bfq0gfq0g fq0;q1gfq0;q1gfq0;q2g fq0;q1;q2gfq0;q2gfq0;q2g fq0;q1;q2gfq0;q1;q2gfq0;q2g fq0;q1;q2gq00q01q02q03abababbaLa déterminisation du second automate conduit au résultat :0a bfq0gfq1g fq2gfq1gfq1g fq0;q2gfq2gfq2g fq0gfq0;q2gfq1;q2g fq0;q2gfq1;q2gfq1;q2g fq0;q2gq00q01q02q03q04ababbabaabCorrigé des exercices4.

5) Exercice 7Seules quatre configurations sont possibles :-les qua trev erresson ttous dans le même sens (configur ationq0);-trois v erresson tdans un sens et le qua trièmedans l" autresens (configur ationq1);-deux v erresv oisinsson tdans un sens et les deux a utresdans l" autresens (configur ationq2);-deux v erresopposés son tdans un sens et les deux a utresdans l" autresens (configur ationq3).On désigne par la lettre :-ale fait de changer l"orientation d"un des quatre verres;-ble fait de changer l"orientation de deux verres voisins;-cle fait de changer l"orientation de deux verres opposés.Le jeu peut alors être représenté par l"automate non déterministe suivant :q0q1q2q3aababcb;ccSa déterminisation conduit à l"automate suivant :012312012013010230212030a;bcacacbacab;cbcacbb;cacacbabOn constate que la succession de mouvementcbcacbcconduit nécessairement à une position gagnante pour lebarman.Exercice 8T(A)et doncA0=D(T(A))reconnait l"image miroir du langage reconnu parA, doncA00reconnaitle même langage que A; il est équivalent à A.On obtient pour A0l"automate :http://info-llg.fr4.6option informatiqueq00q01q02q03q04q05q06ababbabbabbaet pour A00l"automate :q000q001q002aba;bbaExercice 9L"automate non déterministe :q0q1q2q3q4a;babbaa;bse déterminise en :0a bfq0gfq0;q1g fq0gfq0;q1gfq0;q1g fq0;q2gfq0;q2gfq0;q1g fq0;q3gfq0;q3gfq0;q1;q4g fq0gfq0;q1;q4gfq0;q1;q4g fq0;q4gfq0;q4gfq0;q1;q4g fq0;q4gq00q01q02q03q04q05baabababababOn notera que l"étatq05peut être supprimé sans changer le langage reconnu par cet automate.L"algorithme KMP consiste à considérer les états et transitions suivants :a b"a"aa ababa abbabbabba"abbaa abCorrigé des exercices4.7puis à transformer l"état acceptant (abba) en puit :"aababbabbabaabababa;bThéorème deKleeneExercice 10On 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), avecP=fc1;c2;c3;c6;c7g,S =fc5;c6;c7get F =fc21;c22;c1c2;c2c1;c1c3;c2c3;c3c4;c4c5;c26;c27;c6c7;c7c6g.On déduit de l"automate local qui en résulte l"automate deGlushkovde l"expression rationnelle en supprimantle marquage des transitions :c0c3c4c5c2c1c6c7acaaccaaaacbbcaacOn notera que puisque"appartient au langagec0est un état acceptant.

Sa déterminisation fournit l"automatesuivant :q0q1q2q3q4acacbcabExercice 11L"automate suivant reconnait le langage L=nm2jmja0 mod 3o:http://info-llg.fr4.8option informatiqueq0q1q2abababOn lui applique l"algorithme d"élimination des états en éliminant successivementq2,q1etq0:iq0fq1q2ab"abab"iq0fq1ab"abab"iq0fb+ababa""if(b+ababa)L est donc dénoté par (b+ababa).Exercice 12L"automate suivant reconnait le langage L :q0q1q2q3aababaOn le rend complet en ajoutant un état puit :q0q1q2q3q4ababababa;bEn inversant les états acceptants on obtient un automate qui reconnaitL :Corrigé des exercices4.9q0q1q2q3q4ababababa;bExercice 13SiL1etL2sont deux langages reconnus par des automatesA1etA2nous savons calculer lesautomates reconnaissant l"intersection et le complémentaire donc des automates reconnaissantL1nL2etL2nL1.Il reste à utiliser l"équivalence : L1= L2()(L1nL2=;et L2nL1=;) pour conclure.Exercice 14Considérons un automate fini déterministeA= (;Q;q0;F;)qui reconnaitL, notonsAc(respec-tivementCo) l"ensemble des états accessibles (respectivement co-accessibles) et considérons les trois automates :Ap= (;Q;q0;Co;);As= (;Q;Ac;F;);Af= (;Q;Ac;Co;)(les deux derniers sont non déterministes).AlorsApreconnaitpref(L),Afreconnaitsuff(L),Afreconnaitfact(L)(on peut aussi observer quefact(L) =pref(suff(L)).Exercice 15SoitA= (;Q;q0;F;)un automate qui reconnaitL.

Pour toutq2Qon noteIql"ensemble desmots qui étiquètent un chemin deq0àqetFql"ensemble des mots qui étiquètent un chemin deqà l"un des étatsfinaux deF.

Ces deux langages sont respectivement reconnus par(;Q;q0;fqg;)et(;Q;q;F;)donc rationnels.L"égalitépL=[q2QIq\Fqprouve alors quepL est aussi rationnel.Exercice 16SoitA= (;Q;q0;F;)un automate qui reconnait le langageL.

On noteIl"ensemble des étatsaccessibles à partir deq0en suivant un chemin étiqueté par un mot deK.

On considère alors l"automate (nondéterministe) A0= (;Q;I;F;); nous allons montrer que A0reconnait K1L.Considérons un motv2K1Letu2Ktel queuv2L.

Puisqueuv2Lle cheminq0uv qfmène à un étatacceptantqf2F.

Ce dernier se décompose en