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 ) 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 , c'est-à-dire un quadruplet où est l'ensemble des états, l'état initial ( ), l'application de transition et l'ensemble des états finals.
On note le mot vide. Par extension de , on appelle l'application définie pour tout état par et, si est une lettre de et un mot de .
Un automate est représenté par un graphe orienté. Les sommets de ce graphe sont les éléments de . Ce graphe admet un arc étiqueté par la lettre si et seulement si ; de même, ce graphe admet un arc étiqueté par la lettre si et seulement si . 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 d'un automate avec l'ensemble des
entiers compris entre 0 et . On convient de plus que l'état initial est toujours identifié à l'entier 0 . Les automates seront représentés par des triplets ( , 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 à ,
delta, de type (int * int) array de longueur , est un tableau qui stocke les couples ,
f, de type bool array de longueur , 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 ( , 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 et le successeur par la lettre de l'état q (qui est de type int).
if 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 permet de créer un tableau de longueur et initialisé avec la valeur , que Array.copy renvoie une copie d'un tableau , que Array. length t renvoie la longueur d'un tableau . On rappelle enfin que Array.make_matrix n m x permet de créer un tableau de tableaux de taille dont toutes les cases sont initialisées avec la valeur .
1 Premiers exemples
- Donner, sans preuve, une description courte en langue française du langage reconnu par l'automate de la figure 1 . - Donner, sans preuve, une description courte en langue française du langage reconnu par l'automate de la figure 2 . - 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 de la figure 2 . - Écrire en Caml, sans justification, la construction d'une instance du type automate qui corresponde à l'automate de la figure 2 .
Figure 1 - Automate
Figure 2 - Automate
Figure 3 - Automate
Figure 4 - Automate
2 États accessibles d'un automate
- Écrire une fonction numero de type int -> int list -> int array qui, à partir d'un entier et une liste d'entiers compris entre 0 et , renvoie un tableau de taille tel que, pour tout compris entre 0 et , la case de vaut -1 si est absent de et représente l'indice de l'une des occurrences de dans sinon. Par exemple, numero 5 [3;2;0];; peut renvoyer .
Définition : Un état d'un automate est dit accessible s'il existe un mot tel que , autrement dit s'il existe un chemin qui relie l'état initial à l'état dans sa représentation graphique. (On notera que l'état initial est toujours accessible.).
Soit l'ensemble des états accessibles de l'automate . On appelle partie accessible de l'automate le nouvel automate où est la restriction de l'application au domaine .
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. - É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 et . Une application est appelée morphisme d'automates de l'automate vers l'automate , et est notée , si elle satisfait les conditions suivantes :
Indication Caml : En Caml, on représente un morphisme par le tableau de longueur , de type int array, formé d'entiers compris entre 0 et . On pourra utiliser le type morphisme, défini par l'alias
type morphisme = int array;;
3.1 Exemples de morphismes d'automates
À partir des figures 2 et 3 représentant les automates et , recopier le tableau suivant et le compléter sans justification par des états de de sorte que ce tableau représente un morphisme d'automates de l'automate vers l'automate .
10 - À partir des figures 2 et 4 représentant les automates et , donner, sans en justifier l'expression, un morphisme d'automates de l'automate vers l'automate .
11 - À partir des figures 1 et 2 , montrer qu'il n'existe pas de morphisme d'automates de l'automate vers l'automate .
12 - À partir des figures 2 et 5 , montrer qu'il n'existe pas de morphisme d'automates de l'automate vers l'automate .
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 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
Figure 6 - Automate
3.3 Existence de morphismes d'automates entre automates accessibles
- 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. - É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 et deux automates. On appelle automate produit, et on note , le nouvel automate
où l'application est définie, pour tout couple d'états et pour toute lettre .
18 - On considère les automates et qui sont représentés par les figures 3 et 4 . Dessiner, sans justification, la partie accessible du produit d'automates .
19 - Écrire une fonction produit de type automate -> automate -> automate qui renvoie le produit des deux automates donnés en argument.
20 - Soit ( ) un état accessible du produit de deux automates qui acceptent le même langage. Montrer que est un état final du premier automate si et seulement si 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 , et et deux morphismes d'automates et . Le but de cette sous-section est de construire un nouvel automate accessible et trois morphismes et dont la situation est résumée dans le diagramme suivant.
Définition : On définit une relation sur , notée . Pour tout couple d'états ( ) appartenant à s'il existe une suite finie de longueur (avec ) constituée des termes d'états de telle que
- Montrer que la relation définie sur l'ensemble est une relation d'équivalence. - Montrer que, pour tout couple d'états , si , alors, pour toute lettre , on a .
24 - Montrer que, pour tout couple d'états , si , alors est un état final de l'automate si et seulement si est un état final de l'automate .
Définition : La classe d'équivalence, notée , d'un état est l'ensemble
Dans ce qui suit, on appelle le nombre de classes d'équivalence de la relation et on note ces classes. On choisira de sorte que . On note l'application qui, à chaque état , associe la classe d'équivalence .
Indication Caml : En Caml, on représentera la classe d'équivalence par l'indice . - Construire un automate accessible dont l'ensemble d'états est , et tel que est un morphisme d'automates de l'automate vers l'automate . Justifier. - Construire deux morphismes d'automates et , où est l'automate construit à la question 25. - É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 . Le premier élément du résultat doit de plus être égal à 0 . Par exemple renomme ; ; peut renvoyer . Préciser la complexité de la fonction proposée. - Écrire une fonction relation, de type morphisme -> morphisme -> morphisme, qui, à partir des tableaux et , renvoie le tableau , autrement dit, qui renvoie un tableau t d'entiers compris entre 0 et tel que pour tout couple d'états , les valeurs t. (q) et t . (p) sont égales si et seulement si et tel que t . ( 0 ) vaut 0 .
5 Réduction d'automates
5.1 Existence et unicité
- Montrer que si deux automates accessibles et acceptent le même langage, alors on peut construire un automate et deux morphismes et . - Déterminer l'automate défini à la question 29 pour les automates et (figures 3 et 4) et préciser les applications et .
Soit un langage rationnel et l'ensemble des automates (complets déterministes) accessibles qui acceptent le langage . On note le plus petit nombre d'états d'un automate de . - Montrer que deux automates de ayant états sont nécessairement isomorphes. - Montrer que, pour tout automate dans , il existe un morphisme , où est un automate de à états.
5.2 Construction d'un automate réduit par fusion d'états
Définition : Soient et deux automates. On dit que deux états et de l'automate ont été fusionnés dans l'automate s'il existe un morphisme d'automates de vers ' tel que et si le nombre d'état satisfait . - On considère l'automate de la figure 6. Dessiner un automate dans lequel les états et ont été fusionnés. On donnera un morphisme d'automates . - Expliquer brièvement pourquoi il n'est pas possible de construire un automate muni d'un morphisme d'automates tel que . - Quels états faut-il encore fusionner dans pour obtenir un automate à trois états , qui reconnait le même langage que ? - Soit un automate accessible. On appelle le graphe orienté de sommets et, pour toute lettre , d'arcs allant du sommet vers le sommet .
Écrire en Caml une fonction table_de_predecesseurs de type automate -> bool array array qui prend en entrée un automate accessible à états et renvoie en sortie une matrice de taille . Pour tous les états et de l'automate , la valeur de la case ( ) de la matrice vaut true si et seulement s'il existe deux états et un chemin du sommet vers le sommet ( ) dans le graphe tel que et ou et .
On essaiera de ne pas dépasser une complexité en . - 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 associé au langage reconnu par .
Fin de l'épreuve
Mines Option Informatique MP 2019 - Version Web LaTeX | WikiPrépa | WikiPrépa
