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é.