Mines Informatique optionnelle MP 2019

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