Mines Informatique optionnelle MP 2019

Thème de l'épreuve Minimisation d'automates par morphismes
Principaux outils utilisés automates déterministes, parcours en profondeur, langages
Mots clefs dictionnaire, équivalence de Nérode, minimisation d'automates, composantes connexes, morphisme d'automates, partie accessible, automate produit, diagramme d'automates, fusion d'états

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)
        

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


 Mines Informatique optionnelle MP 2019 -- Corrigé Ce corrigé est proposé par Guillaume Batog (professeur en CPGE) ; il a été relu par Olivier Levillain (enseignant-chercheur en école d'ingénieurs) et Benjamin Monmege (enseignant-chercheur à l'université). Le sujet porte sur les automates déterministes avec un alphabet à deux lettres. L'objectif est de construire un automate possédant un minimum d'états et acceptant un langage rationnel donné. La technique employée est élaborée à partir de morphismes d'automates et de parcours en profondeur de graphes. · La première partie est rapide, il s'agit de déterminer des langages acceptés par des automates sur quelques exemples. · La deuxième partie construit la partie accessible d'un automate à partir d'un parcours en profondeur de son graphe sous-jacent. Les trois questions de cette partie sont peu guidées, discriminantes et fatidiques en cas de méconnaissance du cours. Il ne faut pas hésiter à soigner cette partie, d'autant plus qu'elle comporte quelques-unes des rares questions de programmation du sujet. · La troisième partie définit la notion de morphisme entre automates. Après quelques exemples, on établit des propriétés théoriques ­ composition, morphisme inverse, langage accepté ­ avant de coder un test d'existence de morphisme. Il faut réfléchir soi-même à l'algorithme, qui demande une bonne dose d'initiative et d'inspiration sur le parcours en profondeur précédent. · La quatrième partie est longue et répétitive. On construit et manipule les morphismes de façon théorique. Il est possible de traiter les trois questions de programmation indépendamment du reste, notamment la construction d'un automate produit. · La cinquième partie exploite les résultats précédents pour démontrer l'existence et l'unicité (à un isomorphisme près) d'un automate minimal. Sa construction s'appuie sur une technique de fusions d'états, modélisés par des morphismes. Après quelques manipulations sur un exemple, on passe à l'algorithmique et la programmation dans les deux dernières questions. Elles nécessitent énormément de recul, sachant que l'énoncé ne propose à nouveau aucun algorithme. Difficile en trois heures de venir à bout de ce sujet, qui a le mérite d'être complet et bien construit (excepté pour la dernière question). Les exemples et l'ordre des questions sont bien choisis pour assimiler les nouvelles notions. Le programmeur chevronné sera en revanche déçu. En effet, les quelques questions de code sont l'aboutissement d'une réflexion à la fois théorique et algorithmique. Cette épreuve de haut niveau visait à départager les meilleurs. Toutefois, pour ceux moins à l'aise avec la théorie, traiter les questions 1 à 15, puis 18, 19 et 27 en trois heures est tout à fait profitable (et honorable !) pour réviser les automates. Indications Partie 2 6 Parcourir récursivement la liste en argument à l'aide d'une fonction auxiliaire récursive dont un paramètre retient le nombre d'éléments rencontrés. 7 Coder les états visités à l'aide d'un tableau de booléens, puis écrire une fonction auxiliaire récursive parcours telle que parcours q acc réalise le parcours en profondeur à partir du sommet q étant donné la liste acc des sommets accessibles déjà visités. Dans le cadre des automates du sujet, tout état q ne possède que deux voisins (q, a) et (q, b). Ainsi, au maximum deux appels récursifs sont suffisants à chaque étape. 8 Gérer les numéros d'états est le plus délicat. On renumérote les états du parcours en profondeur grâce à la fonction numero de la question 6. Réciproquement, construire un tableau decode permettant de trouver le numéro d'état de l'automate initial à partir de celui de la partie accessible. Partie 3 9 Avoir l'intuition d'un morphisme d'automates comme un processus de fusion d'états et de transitions ayant même origine, destination et étiquette. 11 Raisonner par l'absurde. Les conditions (2) et (4) fixent les images d'un morphisme de A1 vers A2 s'il existe. Toutefois, la condition (3) n'est pas satisfaite. 13 Montrer l'égalité des langages des deux automates par double inclusion. Pour tout mot = 1 2 · · · dans le langage d'un automate A, considérer une exécution de ce mot sur A : 1 2 q1 - q2 - · · · q - q+1 avec qi QA q1 = iA et q+1 FA puis en déduire une exécution de sur l'autre automate. 14 Justifier que est injective. Pour montrer que -1 est un morphisme, vérifier les quatre conditions de morphisme. 16 Montrer que tout état de l'automate B possède un antécédent par par récurrence sur la distance n de cet état à l'état initial. 17 S'inspirer du parcours en profondeur de la question 7 où le tableau visites est remplacé par le tableau phi résultat, -1 signifiant que l'état correspondant n'a pas encore été visité. La condition (3) permet de construire les images de des successeurs d'un état q dont on connaît (q). À chaque étape du parcours, tester l'absence d'incohérence dans la construction de vis-à-vis des conditions de morphisme (3) et (4). Partie 4 19 Coder l'état (q1 , q2 ) par l'entier q1 + n1 q2 avec n1 le nombre d'états du premier automate. Il suffit de parcourir un à un les états de l'automate produit pour construire sa fonction de transition et ses états finals. 20 Pour toute exécution d'un mot sur l'automate produit A × A , construire deux exécutions de sur chacun des automates A et A . 21 Les morphismes considérés sont les projections (x, y) 7 x et (x, y) 7 y. 22 Les trois propriétés d'une relation d'équivalence sont la réflexivité, la symétrie et la transitivité. 23 Considérons la séquence des B (qj , ) pour 0 6 j < k, où q0 , q1 , ..., qk désigne une séquence résultant de la condition p q. 25 L'automate C est « l'image » de l'automate B par le morphisme : q 7- [q]. 26 Suivre les flèches dans le diagramme de début de section 4.2 du sujet. 27 Utiliser un dictionnaire dico de type (int * int) list contenant des couples de la forme (cle,obj) avec cle un entier présent dans le tableau initial et obj le renommage choisi pour cet entier. 28 Déterminer les composantes connexes du graphe où deux sommets p et q sont voisins si et seulement si (p) = (q) ou (p) = (q). Partie 5 29 Employer les questions 21 et 26. 30 D'après le raisonnement de la question 29, utiliser l'automate de la question 18. 31 Justifier que les deux morphismes de la question 29 sont des isomorphismes. 32 Reprendre la construction de morphisme de la question 31. 34 Ne pas oublier la contrainte imposée par la condition (4) de morphisme. 35 Après fusion, justifier qu'on obtient bien un automate ayant un minimum d'états. 36 Réaliser un parcours en profondeur sur le graphe P, qu'on ne construira pas, en s'inspirant de la question 7 où le tableau visites est remplacé par la matrice attendue en sortie. Commencer le parcours à partir de la liste de tous les sommets de F × F F × F. Mettre à jour la matrice visites au cours de l'initialisation de cette liste. 37 Une coquille s'est glissée dans l'énoncé de la question 36. On doit considérer plutôt un graphe P dont les arcs vont de (p, ), (q, ) vers (p, q) pour tous {a, b} et p, q Q. Reprendre alors la construction de la matrice m de la question 36, qui encode la relation d'équivalence suivante sur les états de A : p, q Q pq m.(p).(q) = false L'automate minimal s'obtient en fusionnant les ensembles d'états appartenant à une même classe d'équivalence. On construit d'abord le morphisme qui, à tout état, associe le numéro de sa classe d'équivalence, puis l'automate image de A par en s'inspirant de la question 8. 1. Premiers exemples 1 L'automate A1 accepte le langage L1 des mots de longueur impaire. En effet, toute exécution de l'automate A1 est de la forme 2k+1 1 2 3 2k A - B - A - B · · · -- A ---- B où les lettres i peuvent valoir indifféremment a ou b. 2 L'automate A2 accepte le langage L2 des mots contenant un nombre impair de lettres b. Quel que soit l'état dans lequel on se trouve, l'automate A2 peut lire un nombre quelconque de lettre a, et ce en restant toujours dans le même état courant. Ainsi, il n'existe aucune contrainte sur le nombre ou la position des lettres a dans le langage L2 . En enlevant de A2 les transitions étiquetées par a (non contraignantes), on retrouve l'automate A1 avec la seule lettre b. 3 Le langage L1 est dénoté par l'expression (a + b) · (a + b)2 4 Le langage L2 est dénoté par l'expression a · b · (a · b)2 · a Cette expression rationnelle est composée de trois parties traduisant les étapes d'un cheminement dans l'automate : 1. On arrive une première fois dans l'état D : a · b. 2. On revient possiblement sur l'état D via un détour par l'état C : (a ·b)2 . On applique l'étoile de Kleene à cette expression pour répéter le processus (éventuellement zéro fois). 3. On reste à l'état D, auquel cas on ne peut que boucler sur l'état D final : a . 5 Le code suivant est de type automate et représente l'automate A2 . let n = 2 and delta = [| 0,1 ; 1,0 |] and f = [| false; true |] in n,delta,f;; Les parenthèses d'un n-uplet sont facultatives si aucune ambiguïté d'écriture ne se présente. Rappelons que l'état initial C est codé par 0 d'après l'énoncé.