Réduction d'automates : morphismes et automate produit
Afficher ou masquer la section
Le sujet traite d'une méthode de réduction des automates, en s'appuyant sur la notion formelle d'automate et sur des structures informatiques que le candidat doit manipuler. Il progresse des premiers exemples et de la représentation informatique d'un automate jusqu'à la construction de morphismes d'automates, avant d'aboutir à la réduction d'un automate par fusion d'états.
11. Premiers exemplesDescription qualitative et rationnelle du langage accepté par un automate, puis manipulation de sa représentation informatique.
22. États accessibles d'un automateDétermination des états accessibles par un parcours en profondeur du graphe associé à l'automate.
33. Morphismes d'automatesÉtude des propriétés des morphismes d'automates, avec preuves du caractère bijectif ou surjectif selon les cas.
44. Constructions de morphismes d'automatesConstruction d'un automate produit et d'un diagramme d'automates, avec renumérotation des couples d'états.
55. Réduction d'automatesSynthèse des résultats précédents pour construire un automate réduit par fusion d'états.
Ce qu'a observé le jury
5 erreurs relevées
Confusion entre parcours en profondeur et en largeur · Renumérotation des sommets et transitions mal faite · Contresens sur l'existence d'un morphisme
Afficher ou masquer la section
Le sujet permet de bien évaluer l'acquisition du programme des deux années de classe préparatoire, en combinant la notion formelle d'automate et des structures informatiques complexes. Les candidats abordent l'ensemble des questions dans leur grande majorité et la présentation des copies est globalement satisfaisante, mais le jury constate peu d'efforts de rédaction sur les questions théoriques, avec des arguments souvent absents, superficiels ou ne citant pas les résultats déjà montrés.
Les erreurs les plus sanctionnées
1
Confusion entre parcours en profondeur et en largeurQ7
À la question 7, on constate une confusion avec le parcours en largeur ou l'oubli du marquage des sommets rencontrés, ainsi qu'une estimation asymptotique de la complexité parfois fausse.
2
Renumérotation des sommets et transitions mal faiteQ8
Beaucoup de candidats renumérotent mal les sommets du graphe ou les transitions à la question 8.
« Beaucoup de candidats ont mal renuméroté les sommets du graphe ou les transitions »
3
Contresens sur l'existence d'un morphismeQ9 à Q12
Aux questions 9 à 12, certains candidats trouvent un morphisme alors qu'il est demandé de montrer qu'il n'en existe pas.
« certains candidats trouvent un morphisme alors qu'il est demandé de montrer qu'il n'en existe pas »
4
Preuves formelles peu rigoureusesQ13 à Q16
Les preuves du caractère bijectif ou surjectif d'un morphisme sont souvent confuses et peu rigoureuses, sans citer précisément les propriétés utilisées à chaque étape.
5
Relation d'équivalence mal compriseQ22 à Q28
Aux questions 22 à 28, la relation d'équivalence décrite dans l'énoncé est souvent mal comprise par les candidats.
Ce qui a été bien réussi
Les questions 1 à 4 sur la description du langage accepté par un automate sont globalement comprises.
La question 5 montre que les candidats ont compris la représentation informatique de l'automate choisie dans l'énoncé.
Conseils du jury
Citer explicitement les propriétés et résultats précédemment établis à chaque étape d'une preuve formelle.
Décrire qualitativement l'algorithme avant d'écrire le code, comme le conseille l'énoncé, et commenter le code pour en faciliter la lisibilité.
Bien distinguer parcours en profondeur et parcours en largeur d'un graphe.
Soigner la rédaction des questions théoriques plutôt que de se limiter à des arguments superficiels.
Synthèse rédigée par WikiPrépa à partir du rapport officiel du jury (à télécharger en PDF). Les citations sont extraites du rapport.
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.
Abstract
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.
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 A = ⟨Q, i, δ, F⟩ où Q est l'ensemble des états, i l'état initial ( i ∈ Q ), δ : Q × {a, b} → Q l'application de transition et F ⊆ Q l'ensemble des états finals.
On note ε le mot vide. Par extension de δ, on appelle δ^∗ l'application Q × {a, b}^∗ → Q définie pour tout état q par δ^∗(q, ε) = q et, si σ est une lettre de {a, b} et w un mot de {a, b}^∗, δ^∗(q, σw) = δ^∗(δ(q, σ), w).
Un automate ⟨Q, i, δ, 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) ∈ Q × Q étiqueté par la lettre a si et seulement si δ(p, a) = q; de même, ce graphe admet un arc (p, q) ∈ Q × Q étiqueté par la lettre b si et seulement si δ(p, b) = q. Une flèche venant de nulle part et pointant vers i 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, i, δ, F⟩ avec l'ensemble des
entiers compris entre 0 et |Q| − 1. On convient de plus que l'état initial i 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), δ(q, b))_(q ∈ Q),
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 × 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 × m dont toutes les cases sont initialisées avec la valeur x.
1 Premiers exemples
◻1 - Donner, sans preuve, une description courte en langue française du langage reconnu par l'automate A_1 de la figure 1 . ◻2 - Donner, sans preuve, une description courte en langue française du langage reconnu par l'automate A_2 de la figure 2 . ◻3 - Donner, sans preuve, une expression rationnelle qui dénote le langage reconnu par l'automate A_1 de la figure 1 .
4 - Donner, sans preuve, une expression rationnelle qui dénote le langage reconnu par l'automate A_2 de la figure 2 . ◻5 - Écrire en Caml, sans justification, la construction d'une instance du type automate qui corresponde à l'automate A_2 de la figure 2 .
Figure 1 - Automate A_1
Figure 2 - Automate A_2
Figure 3 - Automate A_3
Figure 4 - Automate A_4
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 A d'entiers compris entre 0 et n − 1, renvoie un tableau T de taille n tel que, pour tout i compris entre 0 et n − 1, la i^(ième) case T[i] de T vaut -1 si i est absent de A et T[i] représente l'indice de l'une des occurrences de i dans A sinon. Par exemple, numero 5 [3;2;0];; peut renvoyer [|2; − 1; 1; 0; − 1|].
Définition : Un état q d'un automate A = ⟨Q_A, i_A, δ_A, F_A⟩ est dit accessible s'il existe un mot w ∈ {a, b}^∗ tel que δ^∗(i_A, w) = q, autrement dit s'il existe un chemin qui relie l'état initial i_A à l'état q dans sa représentation graphique. (On notera que l'état initial i_A est toujours accessible.).
Soit Q^′ l'ensemble des états accessibles de l'automate A. On appelle partie accessible de l'automate A le nouvel automate A^′ = ⟨Q^′, i_A, δ^′, F_A ∩ Q^′⟩ où δ^′ est la restriction de l'application δ_A au domaine Q^′ × {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 - Écrire 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 A = ⟨Q_A, i_A, δ_A, F_A⟩ et B = ⟨Q_B, i_B, δ_B, F_B⟩. Une application φ : Q_A → Q_B est appelée morphisme d'automates de l'automate A vers l'automate B, et est notée φ : A → B, si elle satisfait les conditions suivantes :
Indication Caml : En Caml, on représente un morphisme φ : A → B par le tableau [φ(q)]_(q ∈ Q_A) de longueur |Q_A|, de type int array, formé d'entiers compris entre 0 et |Q_B| − 1. On pourra utiliser le type morphisme, défini par l'alias
type morphisme = int array;;
3.1 Exemples de morphismes d'automates
◻9 − À partir des figures 2 et 3 représentant les automates A_2 et A_3, recopier le tableau suivant et le compléter sans justification par des états de A_2 de sorte que ce tableau représente un morphisme d'automates φ de l'automate A_3 vers l'automate A_2.
q
φ(q)
E
F
G
10 - À partir des figures 2 et 4 représentant les automates A_2 et A_4, donner, sans en justifier l'expression, un morphisme d'automates de l'automate A_4 vers l'automate A_2.
11 - À partir des figures 1 et 2 , montrer qu'il n'existe pas de morphisme d'automates de l'automate A_1 vers l'automate A_2.
12 - À partir des figures 2 et 5 , montrer qu'il n'existe pas de morphisme d'automates de l'automate A_5 vers l'automate A_2.
3.2 Propriétés des morphismes d'automates
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.
14 - Montrer qu'un morphisme φ entre deux automates ayant le même nombre d'états est nécessairement une application bijective et que l'application φ^(− 1) est encore un morphisme d'automates.
On dit dans ce cas que φ est un isomorphisme d'automates.
15 - Montrer que la composition de deux morphismes d'automates est encore un morphisme d'automates.
Figure 5 - Automate A_5
Figure 6 - Automate A_6
3.3 Existence de morphismes d'automates entre automates accessibles
◻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'existence 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 A = ⟨Q_A, i_A, δ_A, F_A⟩ et A^′ = ⟨Q_(A^′), i_(A^′), δ_(A^′), F_(A^′)⟩ deux automates. On appelle automate produit, et on note A × A^′, le nouvel automate
où l'application δ_(A × A^′) est définie, pour tout couple d'états (q, q^′) ∈ Q_A × Q_(A^′) et pour toute lettre σ ∈ {a, b}, parδ_(A × A^′)((q, q^′), σ) = (δ_A(q, σ), δ_(A^′)(q^′, σ)).
18 - On considère les automates A_3 et A_4 qui sont représentés par les figures 3 et 4 . Dessiner, sans justification, la partie accessible du produit d'automates A_3 × A_4.
19 - Écrire une fonction produit de type automate -> automate -> automate qui renvoie le produit des deux automates donnés en argument.
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 q^′ 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.
4.2 Diagramme d'automates
Dans toute la sous-section 4.2, on considère qu'il existe trois automates accessibles A, A^′ et B = ⟨Q_B, i_B, δ_B, F_B⟩ et deux morphismes d'automates φ : B → A et ψ : B → A^′. Le but de cette sous-section est de construire un nouvel automate accessible C et trois morphismes φ^′, ψ^′ et η dont la situation est résumée dans le diagramme suivant.
Définition : On définit une relation sur Q_B, notée ≡. Pour tout couple d'états ( p, q ) appartenant à Q_B^2, p ≡ q s'il existe une suite finie de longueur k + 1 (avec k ∈ ℕ ) constituée des termes p = q_0, q_1, q_2, …, q_k = q d'états de Q_B telle que
◻22 - Montrer que la relation ≡ définie sur l'ensemble Q_B est une relation d'équivalence. ◻23 - Montrer que, pour tout couple d'états (p, q) ∈ Q_B^2, si p ≡ q, alors, pour toute lettre σ ∈ {a, b}, on a δ_B(p, σ) ≡ δ_B(q, σ).
24 - Montrer que, pour tout couple d'états (p, q) ∈ Q_B^2, si p ≡ q, alors p est un état final de l'automate B si et seulement si q est un état final de l'automate B.
Définition : La classe d'équivalence, notée [q], d'un état q ∈ Q_B est l'ensemble
[q] = {p ∈ Q_B; q ≡ p}.
Dans ce qui suit, on appelle ℓ le nombre de classes d'équivalence de la relation ≡ et on note S_0, S_1, …, S_(ℓ − 1) ces classes. On choisira S_0 de sorte que i_B ∈ S_0. On note η l'application Q_B → {S_0, S_1, …, S_(ℓ − 1)} qui, à chaque état q ∈ Q_B, associe la classe d'équivalence [q].
Indication Caml : En Caml, on représentera la classe d'équivalence S_j par l'indice j. ◻25 - Construire un automate accessible C dont l'ensemble d'états est {S_0, S_1, …, S_(ℓ − 1)} et tel que η est un morphisme d'automates de l'automate B vers l'automate C. Justifier. ◻26 - Construire deux morphismes d'automates φ^′ : A → C et ψ^′ : A^′ → C, où C est l'automate construit à la question 25. ◻27 - Écrire une fonction renomme, de type int array -> 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 [|4; 4; 5; 0; 4; 5|]; ; peut renvoyer [|0; 0; 1; 2; 0; 1|]. Préciser la complexité de la fonction proposée. ◻28 - Écrire une fonction relation, de type morphisme -> morphisme -> morphisme, qui, à partir des tableaux [φ(q)]_(q ∈ Q_B) et [ψ(q)]_(q ∈ Q_B), renvoie le tableau [η(q)]_(q ∈ Q_B), autrement dit, qui renvoie un tableau t d'entiers compris entre 0 et ℓ − 1 tel que pour tout couple d'états (p, q) ∈ Q_B^2, les valeurs t. (q) 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 A et A^′ acceptent le même langage, alors on peut construire un automate C et deux morphismes φ^′ : A → C et ψ^′ : A^′ → C. ◻30 - Déterminer l'automate C défini à la question 29 pour les automates A_3 et A_4 (figures 3 et 4) et préciser les applications φ^′ et ψ^′.
Soit L un langage rationnel et 𝔎_L l'ensemble des automates (complets déterministes) accessibles qui acceptent le langage L. On note m_L le plus petit nombre d'états d'un automate de 𝔎_L. ◻31 - Montrer que deux automates de 𝔎_L ayant m_L états sont nécessairement isomorphes. ◻32 - Montrer que, pour tout automate A dans 𝔎_L, il existe un morphisme φ : A → M_L, où M_L est un automate de 𝔎_L à m_L états.
5.2 Construction d'un automate réduit par fusion d'états
Définition : Soient A = ⟨Q_A, i_A, δ_A, F_A⟩ et A^′ = ⟨Q_(A^′), i_(A^′), δ_(A^′), F_(A^′)⟩ deux automates. On dit que deux états p et q de l'automate A ont été fusionnés dans l'automate A^′ s'il existe un morphisme d'automates de A vers A ' tel que φ(p) = φ(q) et si le nombre d'état satisfait |Q_(A^′)| < |Q_A|. ◻33 - On considère l'automate A_6 de la figure 6. Dessiner un automate A_6^(O, P) dans lequel les états O et P ont été fusionnés. On donnera un morphisme d'automates A_6 → A_6^(O, P). ◻34 - Expliquer brièvement pourquoi il n'est pas possible de construire un automate A_6^(Q, R) muni d'un morphisme d'automates ψ : A_6 → A_6^(Q, R) tel que ψ(Q) = ψ(R). ◻35 - Quels états faut-il encore fusionner dans A_6^(O, P) pour obtenir un automate à trois états M_(L_6), qui reconnait le même langage que A_6 ? ◻36 - Soit A = ⟨Q, i, δ, F⟩ un automate accessible. On appelle P le graphe orienté de sommets Q × Q et, pour toute lettre σ ∈ {a, b}, d'arcs allant du sommet (p, q) ∈ Q × Q vers le sommet (δ(p, σ), δ(q, σ)) ∈ Q × Q.
Écrire en Caml une fonction table_de_predecesseurs de type automate -> bool array array qui prend en entrée un automate accessible A = ⟨Q, i, δ, F⟩ à n états et renvoie en sortie une matrice de taille n × n. Pour tous les états p et q de l'automate A, la valeur de la case ( p, q ) de la matrice vaut true si et seulement s'il existe deux états (p_0, q_0) ∈ Q^2 et un chemin du sommet (p_0, q_0) vers le sommet ( p, q ) dans le graphe P tel que p_0 ∈ F et q_0 ∉ F ou p_0 ∉ F et q_0 ∈ F.
On essaiera de ne pas dépasser une complexité en O(n^2). ◻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 A et renvoie l'automate M_L associé au langage L reconnu par A.
Fin de l'épreuve
Questions fréquentes
4 questions
Sur quels chapitres porte l'épreuve d'informatique option MP 2019 ?
Afficher ou masquer la section
Sur quels chapitres porte l'épreuve d'informatique option MP 2019 ?
+
Le sujet porte sur les automates finis, les parcours de graphes, les morphismes d'automates et la construction d'un automate réduit par fusion d'états.
Quelles erreurs le jury a-t-il le plus relevées ?
+
Une confusion entre parcours en profondeur et en largeur, une renumérotation incorrecte des sommets et transitions, et des preuves formelles peu rigoureuses sur les morphismes d'automates.
Ce sujet d'informatique option MP 2019 est-il difficile ?
+
Le rapport ne permet pas de juger précisément le niveau de difficulté global, mais il note que les questions théoriques, notamment sur les morphismes, ont donné lieu à des preuves souvent confuses.
Quelles notions faut-il maîtriser pour le sujet d'informatique option MP 2019 sur les automates ?
+
Il faut maîtriser la notion formelle d'automate, les parcours de graphes, les propriétés des morphismes et savoir manipuler des structures informatiques complexes en Caml.
Pas de description pour le moment
Commentaires• Mines Option Informatique MP 2019
Connectez-vous pour participer aux discussions
Partagez vos avis, posez des questions et échangez avec la communauté
Même chapitre : Structures de données et… (+1)Centrale Option Informatique MP 2013Centrale · 2013Corrigé
Même année, X-ENSX ENS Option Informatique MP 2019X-ENS · 2019Corrigé
Même chapitre : Structures de données et… (+1)CCINP Option Informatique MP 2026CCINP · 2026Sujet seul
Même année, E3AE3A Option Informatique MP 2019E3A · 2019Corrigé.jpg)
.jpg)
.jpg)
.jpg)
