Centrale Informatique optionnelle MP 2017

Thème de l'épreuve Mots synchronisants
Principaux outils utilisés automates, files, parcours de graphe, logique
Mots clefs mot synchronisant, machine, graphe d'automate, SAT, réduction SAT

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                 

Rapport du jury

(télécharger le PDF)
     

Énoncé obtenu par reconnaissance optique des caractères


î. '» Option informatique N 'à, F' _/ MPO tnncuuns EENTHHLE-SUPËLEE 4 heures Calculatrices autorisées N Mots synchronisants Notations -- Pour tout ensemble fini E, on note |E | son cardinal. -- On appelle machine tout triplet (Q, E, 6) où Q est un ensemble fini non vide dont les éléments sont appelés états, E un ensemble fini non vide appelé alphabet dont les éléments sont appelés lettres et 5 une application de Q >< E dans Q appelée fonction de transition. Une machine correspond donc à un automate déterministe complet sans notion d'état initial ou d'états finaux. -- Pour un état q et une lettre :c, on note q.æ : ô(q,æ). -- L'ensemble des mots (c'est--à--dire des concaténations de lettres) sur l'alphabet E est noté E*. -- Le mot vide est noté 5. -- On note ua: le mot obtenu par la concaténation du mot a et de la lettre a:. -- On note 6* l'extension a Q >< E* de la fonction de transition 6 définie par {W EUR Q, 5*(q58) = q V(q,oe,u) EUR Q >< E >< E*, 5*(q,oeu) : 5*(6(q,æ),u) -- Pour un état (1 de Q et un mot m de E*, on note encore q.m pour désigner 5*(q,m). Pour deux états q et q', q' est dit accessible depuis q s'il existe un mot 11. tel que q' : q.u. On dit qu'un mot m de E* est synchronisant pour une machine (Q, E, 6) s'il existe un état 110 de Q tel que pour tout état q de Q, q.m : q0. L'existence de tels mots dans certaines machines est utile car elle permet de ramener une machine dans un état particulier connu en lisant un mot donné (donc en pratique de la « réinitialiser » par une succession précise d'ordres passés a la machine réelle). La partie I de ce problème étudie quelques considérations générales sur les mots synchronisants, la partie Il est consacrée à des problèmes algorithmiques classiques, la partie III relie le problème de la satisfiabilité d'une formule logique à celui de la recherche d'un mot synchronisant de longueur donnée dans une certaine machine et enfin la partie IV s'intéresse à l'étude de l'existence d'un mot synchronisant pour une machine donnée. Les parties 1, H et 111 peuvent être traitées indépendamment. La partie IV, plus technique, utilise la partie Il. Dans les exemples concrets de machines donnés plus loin, l'ensemble d'états peut être quelconque, de même que l'alphabet (E : {0,1}, {a, b,c} .). Par contre, pour la modélisation en Caml, l'alphabet E sera toujours considéré comme étant un intervalle d'entiers [[O,p -- 1]] où p : |E|. Une lettre correspondra donc a un entier entre 0 et p -- l. Un mot de 2* sera représenté par une liste de lettres (donc d'entiers). type lettre == int; ; type mot == lettre list; ; De même, en Caml, l'ensemble d'états Q d'une machine sera toujours considéré comme étant l'intervalle d'entiers [[O,n-- 1]] où n : |Q|. type etat == int;; Ainsi, la fonction de transition 6 d'une machine sera modélisée par une fonction Caml de signature etat --> lettre --> etat. On introduit alors le type machine type machine = { n_etats : int ; n_lettres : int ; delta : etat --> lettre --> etat};; n_etats correspond au cardinal de Q, n_lettres a celui de E et delta a la fonction de transition. Pour une machine nommée M, les syntaxes M.n_etats, M.n_lettres ou M.delta permettent d'accéder a ses différents paramètres. Dans le problème, on suppose que M.delta s'exécute toujours en temps constant. Par exemple, on peut créer une machine M0 a trois états sur un alphabet a deux lettres ayant comme fonction de transition la fonction fO donnée ci--après. 2017-03--06 19:53:58 Page 1/6 (°C) BY-NC-SA let fO etat lettre = match etat,lettre with 0,0 --> 1 \. \. MMD--'HO |--\OÎ--\O|--\ I V MOMOr--\ ! l l l | ] fO : int --> int --> int =  let M0 = { n_etats = 3 ; n_1ettres = 2 ; delta = :EO };; La figure 1 fournit une représentation de la machine M0- 0 0 1 1 Figure 1 La machine M0 On pourra observer que les mots 11 et 10 sont tous les deux synchronisants pour la machine M0- Dans tout le sujet, si une question demande la complexité d'un programme ou d'un algorithme, on attend une complexité temporelle exprimée en O(...). I Considérations générales I.A = Que dire de l'ensemble des mots synchronisants pour une machine ayant un seul état ? Dans toute la suite du problème, on supposera que les machines ont au moins deux états. I.B = On considère la machine M1 représentée figure 2. Donner un mot synchronisant pour M1 s'il en existe un. Justifier la réponse. < - >:_Ï@ CL Figure 2 La machine M1 I. C = On considère la machine M2 représentée figure 3. Donner un mot synchronisant de trois lettres pour ]V[2. On ne demande pas de justifier sa réponse. I.D = Écrire une fonction delta_etoile de signature machine --> etat --> mot --> etat qui, prenant en entrée une machine M, un état q et un mot u, renvoie l'état atteint par la machine M en partant de l'état (] et en lisant le mot u. I.E = Écrire une fonction est_synchronisant de signature machine --> mot --> bool qui, prenant en entrée une machine M et un mot u, dit si le mot u est synchronisant pour M. I .F = Montrer que pour qu'une machine ait un mot synchronisant, il faut qu'il existe une lettre x et deux états distincts de Q, q et q', tels que q.as : q'.æ. I. G = Soit LS (M ) le langage des mots synchronisants d'une machine M : (Q, 2, 5). On introduit la machine des parties M : (Ô, E, 5) où @ est l'ensemble des parties de Q et où 5 est définie par VP c Q, V3: 5 z, â(P,oe) : {5(p,OE), p EUR P} I.G.1) Justifier que l'existence d'un mot synchronisant pour ]V[ se ramène à un problème d'accessibilité de certain(s) états(s) depuis certain(s) état(s) dans la machine des parties. I.G.2) En déduire que le langage LS (M ) des mots synchronisants de la machine M est reconnaissable. 2017-03--06 19:53:58 Page 2/6 OEC BY--NC-SA a, c b, d Figure 3 M2 : une machine a 4 états I.G.3) Déterminer la machine des parties associée à la machine M0 puis donner une expression régulière du langage LS(MO). I.H * Montrer que si l'on sait résoudre le problème de l'existence d'un mot synchronisant, on sait dire, pour une machine M et un état % de M choisi, s'il existe un mot u tel que pour tout état q de Q, le chemin menant de q a q.u passe forcément par (10. II Algorithmes classiques On appellera graphe d'automate tout couple (S, A) où S est un ensemble dont les éléments sont appelés sommets et A une partie de S >< E >< S dont les éléments sont appelés arcs. Pour un arc (q, x, q"), 35 est l' étiquette de l'arc, q son origine et q' son extrémité. Un graphe d'automate correspond donc a un automate non déterministe sans notion d'état initial ou d'état final. Par exemple, avec 2 : {a,b} SO : {0,1,2,3,4,5} A0: {(O,b,0),(O,a,3),(0,b,2),(O,a,1),(1,a,l),(1,a,2),(2,b,1), (2,b,3),(2,b,4),(3,a,2),(4,a,1),(4,b,5),(5,a,1)} le graphe d'automate GO : (SO, A0) est représenté figure 4. Soient s et 5' deux sommets d'un graphe (S,/1). On appelle chemin de 5 vers 5' de longueur EUR toute suite d'arcs (sl,oel,s'l), (52,552, sé), ..., (Sg,æz, 52) de A telle que 51 : s, 52 : s' et pour tout i de [[1,EUR-- 1]], si : 51+1- L'étiquette de ce chemin est alors le mot æ1æ2....rg et on dit que s' est accessible depuis 5. En particulier, pour tout 5 EUR S, 5 est accessible depuis 5 par le chemin vide d'étiquette 5. b --> @-- Figure 4 Le graphe d'automate Go 2017-03--06 19:53:58 Page 3/6 («à BY--NC-SA Dans les programmes à écrire, un graphe aura toujours pour ensemble de sommets un intervalle d'entiers [[0, n--1]] et l'ensemble des arcs étiquetés par E (comme précédemment supposé être un intervalle [[0, p-- 1]]) sera codé par un vecteur de listes d'adjacence V : pour tout 5 E S', V. (s) est la liste (dans n'importe quel ordre) de tous les couples (s', x) tel que (s, au, s') soit un arc du graphe. Pour des raisons de compatibilité ultérieure, les sommets (qui sont, rappelons--le, des entiers) seront codés par le type etat. Ainsi, avec l'alphabet E = {a, b}, la lettre a est codée 0 et la lettre b est codée 1 ; l'ensemble des arcs du graphe GO, dont chaque sommet est codé par son numéro, admet pour représentation Caml : VO : (etat * lettre) list vect = [| [(0,1) ; (3,0) ; (2,1); (1,0)1; [(1,0) ; (2,0)1; [(1,1) ; (3,1); (4,1)1; [(2,0)l ; [(1,0) ; (5,1)l ; [(1 , O)] Il II.A -- On veut implémenter une file d'attente à l'aide d'un vecteur circulaire. On définit pour cela un type particulier nommé file par type 'a file={tab : 'a vect; mutable deb: int; mutable fin: int; mutable vide: bool} deb indique l'indice du premier élément dans la file et fin l'indice qui suit celui du dernier élément de la file, vide indiquant si la file est vide. Les éléments sont rangés depuis la case deb jusqu'à la case précédent fin en repartant a la case 0 quand on arrive au bout du vecteur (cf exemple). Ainsi, on peut très bien avoir l'indice fin plus petit que l'indice deb. Par exemple, la file figure 5 contient les éléments 4, O, 1, 12 et 8, dans cet ordre, avec fin=2 et deb=9. fin deb i i 12 8 7 2 5 3 1 16 3 4 0 1 Figure 5 Un exemple de file où fin < deb On rappelle qu'un champ mutable peut voir sa valeur modifiée. Par exemple, la syntaxe f . deb <-- 0 affecte la valeur 0 au champ deb de la file f. II.A.1) Écrire une fonction ajoute de signature 'a file --> 'a --> unit telle que ajoute f x ajoute x a la fin de la file d'attente f. Si c'est impossible, la fonction devra renvoyer un message d'erreur, en utilisant l'instruction failwith "File pleine". II.A.2) Écrire une fonction retire de signature 'a file --> 'a telle que retire f retire l'élément en tête de la file d'attente et le renvoie. Si c'est impossible, la fonction devra renvoyer un message d'erreur. II.A.3) Quelle est la complexité de ces fonctions '? On considère l'algorithme 1 s'appliquant à un graphe d'automate G = (S, A) et a un ensemble de sommets E (on note n : |S| et 00, vide et rien des valeurs particulières). II.B * Justifier que l'algorithme 1 termine toujours. II. C * Donner la complexité de cet algorithme en fonction de |S | et |A|. On justifiera sa réponse. II.D * Justifier qu'au début de chaque passage dans la boucle « tant que F n'est pas vide », si F contient dans l'ordre les sommets 51,52, ...,s,., alors D{sl] g D{s2] < < Dis,] et D{sr] -- D{51] g 1. ILE * Pour 5 sommet de G, on note dS la distance de E a 5 c'est--à--dire la longueur d'un plus court chemin d'un sommet de E a 5 (avec la convention ds : oo s'il n'existe pas de tel chemin). II.E.1) Justifier brièvement qu'à la fin de l'algorithme, pour tout sommet 5, D{s] # 00 si et seulement si 5 est accessible depuis un sommet de E et que ds { D{s]. Que désigne alors c ? II.E.2) Montrer qu'en fait, a la fin, on a pour tout sommet s, D{s] : ds. Que vaut alors PLS] '? II.F * Écrire une fonction accessibles de signature ((etat*lettre) list) vect --> etat list --> int * int vect * (etat*lettre) vect prenant en entrée un graphe d'automate (sous la forme de son vecteur de listes d'adjacence V) et un ensemble E de sommets (sous la forme d'une liste d'états) et qui renvoie le triplet (c, D, P) calculé selon l'algorithme précédent. Les constantes oo, vide et rien seront respectivement codées dans la fonction accessibles par --1, (--2,--1) et (--1,--1). 2017-03--06 19:53:58 Page 4/6 (°C) BY-NC-SA créer une file d'attente F, vide au départ créer un tableau D dont les cases sont indexées par S et initialisées a 00 créer un tableau P dont les cases sont indexées par S et initialisées a vide créer une variable 0 initialisée a n pour tout 5 EUR E faire insérer s a la fin de la file d'attente F fixer Dis] à () fixer Pis] à rien diminuer c de 1 fin pour tant que F n'est pas vide faire extraire le sommet s qui est en tête de F pour tout arc (s,y, s') EUR A tel que D{s'] : oo faire fixer Dls'] à D{s] + 1 fixer P{s'] a (s,y) insérer s' a la fin de la file d'attente F diminuer c de 1 fin pour fin tant que renvoyer (c,D,P) Algorithme 1 II. G + Écrire une fonction chemin de signature etat --> (etat*lettre) vect --> mot qui, prenant en entrée un sommet s et le vecteur P calculé à l'aide de la fonction accessibles sur un graphe G et un ensemble E, renvoie un mot de longueur minimale qui est l'étiquette d'un chemin d'un sommet de E a s (ou un message d'erreur s'il n'en existe pas). III Réduction SAT On s'intéresse dans cette partie a la satisfiabilité d'une formule logique portant sur des variables propositionnelles 331, ..., $.... On note classiquement /\ le connecteur logique « et », V le connecteur « ou » et f la négation d'une formule f. On appelle littéral une formule constituée d'une variable xi ou de sa négation .il-, on appelle clause une disjonction de littéraux. Considérons une formule logique sous forme normale conjonctive c'est--à--dire sous la forme d'une conjonction de clauses. Par exemple, F1:(aclVÆ2VOE3)A(æ1Voe4)A(æ2væ3\/æ4) est une formule sous forme normale conjonctive formée de trois clauses et portant sur quatre variables proposi-- tionnelles @, @, mg et 554. Soit F une formule sous forme normale conjonctive, composée de n clauses et faisant intervenir m variables. On suppose les clauses numérotées cl, 02, ..., en. On veut ramener le problème de la satisfiabilité d'une telle formule au problème de la recherche d'un mot synchronisant de longueur inférieure ou égale à m sur une certaine machine. On introduit pour cela la machine suivante associée à F : -- Q est formé de mn + n + 1 états, un état particulier noté f et n(m + 1) autres états qu'on notera q... avec (i,j) EUR |Ï1,n]] >< |Ï1,m+ 1]] ; -- E = {0,1} ; -- 5 est défini par . f est un état puits, c'est--à--dire 6(f, O) : 5(f, 1) : f, . pour tout entier i de [[1, n]], 6(Qi,m+la O) : 5(Qi,m+1a 1) : f, 0 pour tout i dans [[1,n]] et j dans [[1,m]], f si le littéral a:j apparaît dans la clause ci q...;1 Sinon 5 0 7 f si le littéral @ apparaît dans la clause ci (qi--J' >_ q- - sinon 1,j+1 III .A + Représenter la machine associée à la formule F1. 2017--03--06 19:53:58 Page 5/6 (:c BY--NC-SA III.B * Donner une distribution de vérité (v1,u2, u3,u4) EUR [[0,1]]4 (la valeur 1),- étant associée à la variable .r,--) satisfaisant F1. Le mot u1u2u3u4 est--il synchronisant '? III. C -- Montrer que tout mot u de longueur m + 1 est synchronisant. À quelle condition sur les qm.u un mot u de longueur m est--il synchronisant '? III.B * Montrer que si la formule F est satisfiable, toute distribution de vérité la satisfaisant donne un mot synchronisant de longueur m pour l'automate. II I .E * Inversement, prouver que si l'automate dispose d'un mot synchronisant de longueur inférieure ou égale à m, F est satisfiable. Donner alors une distribution de vérité convenable. IV Existence On reprend dans cette partie le problème de l'existence d'un mot synchronisant pour une machine M. IV.A * Soit M : (Q, E, 6) une machine. Pour toute partie E de Q et tout mot u de E'", on note E.u : {q.u, q E E}. IV.A.1) Soit u un mot synchronisant de M et u0,u1, ...,u,. une suite de préfixes de u rangés dans l'ordre croissant de leur longueur et telle que ur : u. Que peut--on dire de la suite des cardinaux |Q.ui| '? IV.A.2) Montrer qu'il existe un mot synchronisant si et seulement s'il existe pour tout couple d'états (q, q') de Q2 un mot uq'q, tel que q.uq'q, : q'.uq7q,. On veut se servir du critère établi ci--dessus pour déterminer s'il existe un mot synchronisant. Pour cela, on associe a la machine M la machine M : (Q, E, 6) définie par : -- @ est formé des parties a un ou deux éléments de Q ; -- Sest définie par V(E,æ) EUR Ô>< E, Ë(E) : {5(q,æ), q E E}. IV.E * Si n : |Q|, que vaut % : |ô| ? IV. C * On a dit que pour la modélisation informatique, l'ensemble d'états d'une machine doit être modélisée par un intervalle [[0, n -- 1]]. @ doit donc être modélisé par l'intervalle [[O,ñ -- 1]]. Soit go,, une bijection de @ sur [[0, ñ-- 1]]. On suppose qu'on dispose d'une fonction set_to_nb de signature int --> (etat list) --> etat telle que set_to_nb n EUR pour n élément de N* et EUR liste d'états renvoie {an({i}) si EUR = m avec i & [[0,n-- 1]] «pn({i,j}) si EUR = {ml avec (M") EUR [[OEn-- 1]]2, 1"  etat --> (etat list) telle que nb_to_set n q pour n élément de N* et q élément de [[O,ñ -- 1]] renvoie une liste d'états de la forme {i] ou {i, j] (avec i < j) correspondant à  etat --> lettre --> etat qui prenant en entrée une machine M, un état q-- de @ et une lettre a:, renvoie l'état de @ atteint en lisant la lettre a: depuis l'état (] dans M. I V.D * Il est clair qu'à la machine llÎ, on peut associer un graphe d'automate 5 dont l'ensemble des sommets est @ et dont l'ensemble des arcs est {(q, a:, 5(q, du)), (q, 33) EUR Ô>< 2}. On associe alors à âle graphe retourné Ô'VR qui a les mêmes sommets que 5 mais dont les arcs sont retournés (ie (q, 35, q') est un arc de ÛR si et seulement si (q',a:,q) est un arc de (?). Écrire une fonction retourne_machine de signature machine --> ((etat*lettre) list) vect qui à partir d'une machine M, calcule le vecteur Vdes listes d'adjacence du graphe 5R. I V.E * Justifier qu'il suffit d'appliquer la fonction accessibles de la partie H au graphe âR et à l'ensemble des sommets de 5R correspondant à des singletons pour déterminer si la machine M possède un mot synchro nisant. IV.F * Écrire une fonction existe_synchtonisant de signature machine --> bool qui dit si une machine possède un mot synchronisant. Jan Ôernÿ, chercheur slovaque, a conjecturé au milieu des années 60 que si une machine a n états possédait un mot synchronisant, elle en avait un de longueur inférieure ou égale à (n-- 1)2. La construction faite dans la partie III afiîrme que la recherche, dans une machine, d'un mot synchronisant de longueur inférieure ou égale à une valeur m fixée est au moins aussi difficile en terme de compleæité que celui de la satisfiabilité d'une formule logique à m variables sous forme normale conjonctive (qu 'on sait être un problème « diflîcile »). oooFlNooo 2017--03--06 19:53:58 Page 6/6 ,@c BY--NC-SA

Extrait du corrigé obtenu par reconnaissance optique des caractères


 Centrale Informatique optionnelle MP 2017 Corrigé Ce corrigé est proposé par William Aufort (ENS Lyon) ; il a été relu par Martin Guy (ENS Lyon) et Benjamin Monmege (enseignant-chercheur à l'université). Cette épreuve est consacrée aux aspects théorique et algorithmique des mots synchronisants associés à une machine. Une machine se comporte comme un automate fini, hormis le fait qu'on ignore les états initial et finals. La notion de mot synchronisant est importante en théorie des automates et apparaît la première fois dans un problème naturel : comment réinitialiser un système ayant un nombre fini d'états sans savoir dans quel état il se trouve ? Le sujet comporte quatre parties, dont les trois premières sont indépendantes. · La première partie étudie quelques propriétés générales des mots synchronisants, notamment le fait que l'ensemble des mots synchronisants d'une machine forme un langage reconnaissable. Il y est question à la fois d'étude d'exemples, de questions d'implémentation plutôt faciles, et de questions utilisant des raisonnements proches de ceux sur les automates. · La deuxième partie, purement algorithmique, a pour objectif l'implémentation d'un algorithme qui détermine l'ensemble des sommets s d'un graphe d'automate accessibles à partir d'un ensemble d'états E donné, ainsi qu'un moyen d'obtenir un plus court chemin de E à s. Tout d'abord, on implémente une structure de file à l'aide d'un tableau circulaire. Puis on étudie un algorithme dont le principe est de parcourir en largeur le graphe, en mettant à jour des structures supplémentaires permettant de retrouver les plus courts chemins. Cette partie comporte beaucoup de questions d'implémentation et de questions relatives à la correction, la terminaison et la complexité des algorithmes. · Dans la troisième partie, on construit à partir d'une formule booléenne quelconque une machine dont on montre qu'elle admet un mot synchronisant d'une certaine longueur si et seulement si la formule est satisfiable. Cette partie mêle donc des raisonnements de théorie des automates et de logique. · Enfin, la quatrième partie permet de résoudre le problème de l'existence d'un mot synchronisant en utilisant la partie II. Elle contient des questions plus avancées sur les automates et des questions d'implémentation. Le sujet est très bien écrit et permet de manipuler toutes les notions du nouveau programme d'informatique optionnelle (automates, graphes, algorithmique et calcul propositionnel). Cela en fait un sujet très intéressant pour la préparation aux épreuves d'informatique. Indications I.B Raisonner sur la parité de l'état q.m. I.E Il suffit de vérifier que l'état q.m est le même pour tout état q. I.F Si u est synchronisant, considérer deux « calculs » partant d'états différents de la machine sur l'entrée u. b I.G.1 Reformuler la propriété « admettre un mot synchronisant » en utilisant . I.G.2 Construire un automate qui reconnaît LS(M) à partir de la machine des parties, en utilisant la propriété établie à la question I.G.1. I.G.3 « Simplifier » l'automate construit avant d'en déterminer le langage. I.H On peut détecter qu'un chemin passe par q0 dans une machine où q0 est un état puits. II.A Attention à la gestion des indices de début et de fin de file. II.B Montrer qu'un sommet est inséré au plus une fois dans la file. II.C La complexité de l'algorithme dépend du nombre de sommets insérés dans la file et du nombre d'arcs parcourus. II.D Montrer le résultat par récurrence sur le nombre de tours de boucle effectués. II.E.1 Observer que quand l'algorithme change le contenu de D[s], cela provient de la découverte d'un chemin de E à s d'une certaine longueur. II.E.2 Raisonner par récurrence sur la valeur de ds . On pourra raisonner par l'absurde et obtenir une contradiction en utilisant le prédécesseur de s dans un plus court chemin de E à s, ainsi que le sommet défilé juste avant l'insertion de s dans la file. II.G Utiliser la question II.E.2 pour construire le mot de longueur minimale de façon récursive. III.A Suivre la définition de la machine donnée au début de la partie. Dans une telle machine, une transition depuis l'état qi,j correspond à la recherche de la variable xj dans la clause i. III.C Remarquer que les états accessibles à partir de qi,j en une transition sont qi,j+1 (s'il existe) et f , puis généraliser cette remarque. III.D Utiliser le lien entre l'appartenance d'un littéral dans une clause et les transitions de la machine. III.E Raisonner comme à la question III.D. Penser à compléter le mot synchronisant de la machine pour obtenir une distribution de vérité totale. IV.A.1 Montrer que cette suite est décroissante et calculer |Q.ur |. IV.A.2 Pour l'implication réciproque, la propriété dit qu'on peut synchroniser deux états quelconques. On peut chercher ensuite à synchroniser trois états, puis formuler une récurrence pour synchroniser tous les états. IV.C Les fonctions nb_to_set et set_to_nb permettent de passer entre les représentations de q par un entier et par un ensemble d'états. e R. IV.D Attention au nombre d'états du graphe retourné G IV.E Reformuler la caractérisation de la question IV.A.2 en terme d'accessibilité e R. dans le graphe G IV.F Implémenter la méthode proposée à la question IV.E. I. Considérations générales I.A Soit M une machine ayant un seul état, que l'on note q. Pour tout mot m de , on a nécessairement q.m = q, donc m est un mot synchronisant. Par conséquent, Tout mot est synchronisant pour une machine à un état. Il faut bien comprendre qu'un mot m est synchronisant si, en partant de n'importe quel état de la machine et en lisant m, on tombe toujours sur le même état. I.B Remarquons qu'une transition dans la machine M1 change la parité de l'état courant. Pour tout m , 1.m et 2.m ont alors des parités opposées. Or, si m est un mot synchronisant, 1.m = 2.m, ce qui est impossible. Finalement, M1 n'admet aucun mot synchronisant. I.C Considérons le mot de trois lettres bcb. On a 1.bcb = 1.cb = 4.b = (4, b) = 4 2.bcb = 1.cb = 4 De même, 3.bcb = 4.cb = 3.b = (4, b) = 4 4.bcb = 4.cb = 4 ce qui prouve que bcb est un mot synchronisant pour M2 . I.D Pour implémenter la fonction delta_etoile, on suit la définition récursive de rappelée dans l'énoncé : si le mot est vide, on renvoie l'état en entrée, sinon on fait une étape de calcul avec , et le reste du calcul est traité par appel récursif. let rec delta_etoile machine etat mot = match mot with | [] -> etat | x::u -> delta_etoile machine (machine.delta etat x) u;; I.E On utilise directement la définition d'un mot synchronisant : on veut vérifier, étant donné un mot m, s'il existe un état q0 tel que pour tout état q, q.m = q0 . On trouve cet état q0 en partant d'un état quelconque de la machine, par exemple 0, et en lisant m, soit q0 = 0.m. Il reste à vérifier la propriété pour tous les autres états à l'aide d'une fonction récursive. let est_synchronisant machine mot = let etat_zero = delta_etoile machine 0 mot in let rec verifie_etat machine mot etat = if etat = 0 then true else if (delta_etoile machine etat mot <> etat_zero) then false else verifie_etat machine mot (etat-1) in verifie_etat machine mot (machine.n_etats-1);; On pourrait aussi utiliser une boucle while décroissante indicée par l'état à vérifier à l'aide d'une référence. On utilise une autre référence pour détecter si un état ne vérifie pas la propriété, auquel cas on peut sortir de la boucle directement. La boucle while simule alors la fonction auxiliaire récursive précédente. let est_synchronisant_imperatif machine mot = let etat_zero = delta_etoile machine 0 mot and etat = ref (machine.n_etats-1) and continue = ref true in while (!continue && !etat > 0) do if (delta_etoile machine !etat mot <> etat_zero) then continue := false else etat := !etat-1 done; !continue;; I.F Soit M une machine ayant un mot synchronisant u = u1 · · · un . Soient q0 et q0 deux états de M distincts (c'est possible car M a au moins deux états). Notons i {1, . . . , n} qi = q0 .(u1 · · · ui ) et qi = q0 .(u1 · · · ui ) les états successivement rencontrés en lisant le mot u à partir des états q0 et q0 respectivement. Soit i le plus grand entier inférieur ou égal à n tel que qi 6= qi . Comme u est synchronisant, qn = q0 .u = q0 .u = qn . De plus, q0 6= q0 . Ceci prouve que i est bien défini. On pose enfin q = qi , q = qi et x = ui+1 . Par définition q 6= q , et q.x = qi .ui+1 = qi+1 = qi+1 = q .x. Ainsi, Une condition nécessaire d'existence d'un mot synchronisant est donnée par x q Q q Q q 6= q et q.x = q .x De manière informelle, ce résultat dit que si une machine admet un mot synchronisant, alors il existe une lettre qui synchronise deux états différents de la machine. La question IV.A.2 montre un résultat similaire mais sous forme de condition nécessaire et suffisante. I.G.1 De la même manière que pour , on peut étendre la fonction de transition b en b × , que l'on note b . M admet un mot synchronisant si et seuleune fonction de Q ment s'il existe un mot u et un état q0 Q tel que pour tout état q Q, q.u = q0 , b b (Q, u) = {q0 }. Autrement dit, ce qui équivaut à dire que, dans la machine M, M admet un mot synchronisant si et seulement si il existe b un état singleton {q0 } accessible depuis l'état Q. dans M Pour prouver qu'un langage est reconnaissable, une méthode générale consiste à exhiber un automate fini qui reconnaît ce langage. Cette méthode semble particulièrement intéressante ici car la notion de machine est très proche de celle d'automate. b où I = Q b , I, F, ) À une machine M, on associe l'automate déterministe AM = (Q, est l'état initial de l'automate et F = {{q}, q Q}, constitué des singletons, est l'ensemble des états finals de l'automate. Un mot u est reconnu par l'automate AM si et seulement si b (Q, u) F, ce qui d'après la question I.G.1 revient à dire que u est I.G.2