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)
        

Énoncé obtenu par reconnaissance optique des caractères


A2019 -- INFO MP

Cm

Concours commun

Mines-Ponts

ÉCOLE DES PONTS PARISTECH,
ISAE-SUPAERO, ENSTA PARISTECH,
TELECOM PARISTECH, MINES PARISTECH,
MINES SAINT-ÉTIENNE, MINES NANCY,
IMT Atlantique, ENSAE PARISTECH,
CHIMIE PARISTECH.

Concours Centrale-Supélec (Cycle International),
Concours Mines-Télécom, Concours Commun TPE/EIVEP.

CONCOURS 2019
ÉPREUVE D'INFORMATIQUE MP

Durée de l'épreuve : 3 heures

L'usage de la calculatrice et de tout dispositif électronique est interdit.

Cette épreuve concerne uniquement les candidats de la filière MP.
Les candidats sont priés de mentionner de façon apparente
sur la première page de la copie :
INFORMATIQUE - MP
L'énoncé de cette épreuve comporte 10 pages de texte.
Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur

d'énoncé, il le signale sur sa copie et poursuit sa composition en expliquant 
les
raisons des initiatives qu'il est amené à prendre.
Épreuve d'option informatique MP 2019

L'épreuve est composée d'un unique problème, comportant 37 questions. Après un
préliminaire, ce problème est divisé en 5 parties. Pour répondre à une 
question, un
candidat pourra réutiliser le résultat d'une question antérieure, même s'il 
n'est pas
parvenu à démontrer ce résultat.

Le but du problème est d'étudier les relations qui existent entre des automates 
qui
reconnaissent un même langage grâce à la notion de morphismes d'automates.

Préliminaires

Concernant la programmation

Il faudra coder des fonctions à l'aide du langage de programmation Caml, tout 
autre
langage étant exclu. Lorsque le candidat écrira une fonction, il pourra faire 
appel à d'autres
fonctions définies dans les questions précédentes ;: il pourra aussi définir 
des fonctions
auxiliaires. Quand l'énoncé demande de coder une fonction, il n'est pas 
nécessaire de
justifier que celle-ci est correcte, sauf si l'énoncé le demande explicitement. 
Enfin, si les
paramètres d'une fonction à coder sont supposés vérifier certaines hypothèses, 
il ne sera
pas utile de tester si les hypothèses sont bien vérifiées dans le code de la 
fonction.

Dans tout l'énoncé, un même identificateur écrit dans deux polices de caractères
différentes désignera la même entité, mais du point de vue mathématique pour la 
police
en italique (par exemple n) et du point de vue informatique pour celle en 
romain avec
espacement fixe (par exemple n).

Définition mathématique d'un automate

Définition : Dans l'ensemble du sujet, le terme automate désigne un automate 
fini
déterministe complet sur l'alphabet {a,b}, c'est-à-dire un quadruplet À = 
(Q,i,0, F) où
Q est l'ensemble des états, à l'état initial (4 EUR Q), Ô : Q X {a,b} -- Q 
l'application de
transition et FC Q l'ensemble des états finals.

On note EUR le mot vide. Par extension de 6, on appelle 6* l'application Q x 
{a,b}* -- Q
définie pour tout état qg par 0*(q,EUR) = q et, si o est une lettre de {a,b} et 
w un mot de
{a,bF*, d*(q,ow) = 0*(0(g,o),w).

Un automate (Q,1,0,F) est représenté par un graphe orienté. Les sommets de ce
graphe sont les éléments de Q. Ce graphe admet un arc (p,q) EUR Q x Q étiqueté 
par la
lettre a si et seulement si 0(p, a) = q; de même, ce graphe admet un arc (pq) 
EQXQ
étiqueté par la lettre b si et seulement si 0(p,b) -- q. Une flèche venant de 
nulle part et
pointant vers ? indique l'état initial. Un état final est représenté par un 
double cercle.

Représentation d'automate en Caml

Indication Caml : Dans toutes les questions demandant d'implémenter une 
fonction en
Caml, on identifie l'ensemble des états Q d'un automate (Q, à, 6, F) avec 
l'ensemble des

Page 1 sur 10
Épreuve d'option informatique MP 2019

entiers compris entre 0 et [Q] -- 1. On convient de plus que l'état initial + 
est toujours
identifié à l'entier 0. Les automates seront représentés par des triplets (n, 
delta, f) où
-- n, de type int, est le nombre d'états de l'automate; les états de l'automate 
sont
les entiers de 0 à n-1,
-- delta, de type (int * int) array de longueur n, est un tableau qui stocke les
couples (ô(q,a),0(q, b) eo:
-- f, de type bool array de longueur n, est un tableau qui représente la 
fonction
indicatrice de l'ensemble des états finals.

Dans l'ensemble du sujet, le type automate est défini par l'alias suivant.
type automate = int * (int * int) array * bool array;;
Ci-dessous sont donnés quelques exemples de son utilisation.

-- let (n, delta, f) = aut in ...
permet de récupérer les composantes d'une variable aut de type automate.

-- let (succ a,succ b) = delta.(q) in ...
permet ensuite de récupérer le successeur par la lettre a et le successeur par 
la
lettre b de l'état q (qui est de type int).

-- if f.(q) then ...
permet de tester si l'état q (qui est de type int) est final.

Indication Caml : On rappelle que la fonction List.length, de type 'a list -> 
int,
renvoie la longueur d'une liste. On rappelle que Array.make n x permet de créer 
un
tableau de longueur n et initialisé avec la valeur x, que Array.copy t renvoie 
une copie
d'un tableau t, que Array.length t renvoie la longueur d'un tableau t{. On 
rappelle enfin
que Array.make matrix n m x permet de créer un tableau de tableaux de taille n 
x m
dont toutes les cases sont initialisées avec la valeur x.

1 Premiers exemples

CT] 1 --- Donner, sans preuve, une description courte en langue française du
langage reconnu par l'automate À; de la figure 1.

CT] 2 -- Donner, sans preuve, une description courte en langue française du
langage reconnu par l'automate 4 de la figure 2.

[] 3 -- Donner, sans preuve, une expression rationnelle qui dénote le langage
reconnu par l'automate À; de la figure 1.

[] 4 -- Donner, sans preuve, une expression rationnelle qui dénote le langage
reconnu par l'automate 4; de la figure 2.

[] 5 -- Écrire en Caml, sans justification, la construction d'une instance du
type automate qui corresponde à l'automate 4, de la figure 2.

Page 2 sur 10
Épreuve d'option informatique MP 2019

FIGURE 4 --- Automate 44

Page 3 sur 10
Épreuve d'option informatique MP 2019

2 États accessibles d'un automate

[] 6 -- Écrire une fonction numero de type int -> int list -> int array
qui, à partir d'un entier n et une liste À d'entiers compris entre OU etn--l,
renvoie un tableau T de taille n tel que, pour tout à compris entre 0 et n -- 
1],
la 20e case T{i] de T vaut --1 si à est absent de À et T{i] représente l'indice
de l'une des occurrences de à dans À sinon. Par exemple, numero 5 [3;2;0];;
peut renvoyer [12; -1; 1; O; -11].

Définition : Un état q d'un automate À = (Q 1,14,04, F4) est dit accessible 
s'il existe
un mot w EUR {a,b}* tel que 0*(i4,w) = q, autrement dit s'il existe un chemin 
qui relie
l'état initial 4 4 à l'état qg dans sa représentation graphique. (On notera que 
l'état initial 4
est toujours accessible. ).

Soit Q' l'ensemble des états accessibles de l'automate À. On appelle partie 
accessible
de l'automate À le nouvel automate 4' = (Q',1i4,0", Fa N Q") où 0' est la 
restriction de
l'application 0 4 au domaine Q' X {a,b}.

On dit qu'un automate est accessible lorsque tous ses états sont accessibles.

[] 7 - Écrire une fonction etats _ accessibles, de type automate -> int list,
qui renvoie la liste des états accessibles de l'automate donné en argument et
que l'on obtient par un parcours de graphe en profondeur depuis l'état initial.
La liste renvoyée doit suivre l'ordre dans lequel les états sont rencontrés pour
la première fois et ne doit pas contenir de doublons. Donner la complexité de
la fonction écrite.

[] 8 - Ecrire une fonction partie _ accessible de type automate -> automate
qui construit la partie accessible de l'automate donné en argument. On pourra
réemployer les fonctions implémentées aux questions 6 et 7.

3 Morphismes d'automates

Définition : Soient deux automates À -- (Q 1,14, 04, F1) et B -- (Q8,ig, 08, 
F8). Une
application & : Q1 -- O8 est appelée morphisme d'automates de l'automate À vers
l'automate B, et est notée w : À -- B, si elle satisfait les conditions 
suivantes :

w est surjective, (1)

p(iA) = ir; (2)

VaE Qu, VoE{a,b}, v(4(g.o)) = ds(v(g). 0), (3)
VE Qx qE Fa > v(0) EUR Fr (4)

Page 4 sur 10
Épreuve d'option informatique MP 2019

Indication Caml :

et [Qg| -- 1. On pourra utiliser le type morphisme, défini par l'alias

3.1

3.2

type morphisme = int array;;

Exemples de morphismes d'automates

[] 9 - À partir des figures 2 et 3 représentant les automates 4 et 43, recopier
le tableau suivant et le compléter sans justification par des états de 4 de
sorte que ce tableau représente un morphisme d'automates 4 de l'automate 43
vers l'automate 4).

(q)

QT Ge

[1 10 -- À partir des figures 2 et 4 représentant les automates 4) et A4, 
donner.
sans en justifier l'expression, un morphisme d'automates de l'automate A4;
vers l'automate 4).

[1 11 -- À partir des figures 1 et 2, montrer qu'il n'existe pas de morphisme
d'automates de l'automate À, vers l'automate 4.

[1 12 -- À partir des figures 2 et 5, montrer qu'il n'existe pas de morphisme
d'automates de l'automate À vers l'automate 4.

Propriétés des morphismes d'automates

CT 13 -- Montrer que deux automates acceptent le même langage dès lors qu'il
existe un morphisme d'automates de l'un des automates vers l'autre.

CT 14 -- Montrer qu'un morphisme & entre deux automates ayant le même
nombre d'états est nécessairement une application bijective et que l'applica-
tion w"{ est encore un morphisme d'automates.

On dit dans ce cas que 4 est un isomorphisme d'automates.

C] 15 -- Montrer que la composition de deux morphismes d'automates est
encore un morphisme d'automates.

Page 5 sur 10

En Caml, on représente un morphisme © : À -- B par le ta-
bleau [w(q)l4eo, de longueur [Q 4}, de type int array, formé d'entiers compris 
entre 0
Épreuve d'option informatique MP 2019

FIGURE 5 -- Automate A;

FIGURE 6 -- Automate A4

Page 6 sur 10
Épreuve d'option informatique MP 2019

3.3 Existence de morphismes d'automates entre automates
accessibles

[1 16 -- Montrer que le point (1) de la définition des morphismes d'automates
découle des points (2), (3) et (4) quand les deux automates considérés sont
accessibles.

[] 17 -- Écrire en Caml une fonction existe morphisme de type automate ->
automate -> bool * morphisme qui, sous l'hypothèse que les deux automates
en argument sont accessibles, renvoie d'une part un booléen indiquant l'exis-
tence d'un morphisme d'automates du premier argument vers le second et
d'autre part un tel morphisme lorsqu'il existe. Lorsqu'un tel morphisme
n'existe pas, la seconde composante de la valeur de retour est un tableau
quelconque. On pourra expliquer le principe de l'algorithme avant d'en donner
le code.

4 Constructions de morphismes d'automates

4.1 Automate produit

Définition : Soient À = (Q 1,14, 04, Fa) et À = (Qw,ix,0w, Fx) deux automates.
On appelle automate produit, et on note À X 4", le nouvel automate

A x À -- (Q A X Qu, (ia, ta), daxar, Fa X Fr)

où l'application Ô4+4 est définie, pour tout couple d'états (q,q') EUR Q4 x Qx 
et pour
toute lettre & EUR {a,b}, par d 4x ((q, q'),o) = (d4(q,o), Ôw(q',o)).

[CT 18 -- On considère les automates 43 et A4 qui sont représentés par les
figures 3 et 4. Dessiner, sans justification, la partie accessible du produit
d'automates A2 X 44.

[1 19 -- Ecrire une fonction produit de type automate -> automate -> automate
P VP
qui renvoie le produit des deux automates donnés en argument.

[1 20 -- Soit (q,q') un état accessible du produit de deux automates qui
acceptent le même langage. Montrer que q est un état final du premier
automate si et seulement si qg' est un état final du second automate.

[] 21 --- Montrer qu'il existe toujours un morphisme d'automates de la partie

accessible du produit de deux automates accessibles qui acceptent le même
langage vers chacun de ces deux automates.

Page 7 sur 10
Épreuve d'option informatique MP 2019

4.2 Diagramme d'automates

Dans toute la sous-section 4.2, on considère qu'il existe trois automates 
accessibles À,
À et B = (Q8,ig, 08, F8) et deux morphismes d'automates 4 : B -- A et D: B -- À.
Le but de cette sous-section est de construire un nouvel automate accessible C 
et trois
morphismes &w', d" et n dont la situation est résumée dans le diagramme suivant.

Définition : On définit une relation sur Q3, notée =. Pour tout couple d'états 
(p, q)
appartenant à Q$, p = q s'il existe une suite finie de longueur k + 1 (avec k 
EUR N)
constituée des termes p = qo,4q1,Qq2,...,qx = q d'états de O3 telle que

VOL j int array, qui
renomme le contenu d'un tableau contenant des entiers positifs prenant
{ valeurs distinctes en utilisant les entiers entre 0 et { -- 1. Le premier 
élément
du résultat doit de plus être égal à 0. Par exemple renomme [14;4;5;0;4;51];;
peut renvoyer [10;0;1;2;0;11]. Préciser la complexité de la fonction proposée.

[] 28 -- Écrire une fonction relation, de type morphisme -> morphisme ->
morphisme, qui, à partir des tableaux [o(q)licox et [V(q)l4eos, renvoie le
tableau |n(q)l4eo,, autrement dit, qui renvoie un tableau + d'entiers compris
entre 0 et { -- 1 tel que pour tout couple d'états (p,q) EUR Q%. les valeurs t. 
(a)
et t.(p) sont égales si et seulement si p = q et tel que t.(0) vaut 0.

5 Réduction d'automates

5.1 Existence et unicité

[] 29 --- Montrer que si deux automates accessibles À et 4' acceptent le
même langage, alors on peut construire un automate C et deux morphismes

w':A--=Cet d': 4 -0C.
[] 30 -- Déterminer l'automate EUR défini à la question 29 pour les automates 4:
et À, (figures 3 et 4) et préciser les applications 4 et 4".

Soit L un langage rationnel et Rz l'ensemble des automates (complets 
déterministes)
accessibles qui acceptent le langage L. On note m, le plus petit nombre d'états 
d'un
automate de fr.

CT 31 -- Montrer que deux automates de Rz ayant mx états sont nécessaire-
ment isomorphes.

[] 32 - Montrer que, pour tout automate A dans fr. il existe un mor-
phisme 6 : À -- M, où M, est un automate de Rz à my, états.

Page 9 sur 10
Épreuve d'option informatique MP 2019

5.2 Construction d'un automate réduit par fusion d'états

Définition : Soient À = (Q 4,14, 04, Fa) et À = (Qw,ix,0w, Fx) deux automates.
On dit que deux états p et q de l'automate À ont été fusionnés dans l'automate 
A4 s'il
existe un morphisme d'automates de À vers 4' tel que w(p) = w(a) et si le 
nombre d'état

satisfait |Q | < [Q4l.

[1 33 -- On considère l'automate 4, de la figure 6. Dessiner un automate ALT
dans lequel les états O et P ont été fusionnés. On donnera un morphisme
d'automates 46 -- AQT.

[] 34 -- Expliquer brièvement pourquoi il n'est pas possible de construire
un automate AL muni d'un morphisme d'automates Y : A5 -- AR tel

que #(Q) = v(R).

CT 35 --- Quels états faut-il encore fusionner dans ACT pour obtenir un
automate à trois états M7,, qui reconnait le même langage que A ?

[1 36 - Soit À = (Q,i,0,F) un automate accessible. On appelle P le graphe
orienté de sommets Q x Q et, pour toute lettre o& EUR {a,b}, d'arcs allant du
sommet (p,q) EUR Q x Q vers le sommet (ô(p,o),0(q,a)) EUR Q x Q.

Écrire en Caml une fonction table de _ predecesseurs de type automate ->
bool array array qui prend en entrée un automate accessible À = (Q,i, 0, F)
à n états et renvoie en sortie une matrice de taille n x n. Pour tous les états 
p
et q de l'automate À, la valeur de la case (p, q) de la matrice vaut true si et
seulement s'il existe deux états (po, go) EUR Q° et un chemin du sommet (po, qo)
vers le sommet (p,q) dans le graphe P tel que po EUR F et 4 Four é F'et
do EUR F.

On essaiera de ne pas dépasser une complexité en O(n).
[] 37 -- En décrire le principe, le justifier, puis écrire en Caml une fonction

reduit, de type automate -> automate qui prend en entrée un automate À et
renvoie l'automate M, associé au langage L reconnu par À.

FIN DE L'ÉPREUVE

Page 10 sur 10

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