Mines Informatique MP 2007

Thème de l'épreuve Expressions rationnelles, langages locaux, algorithme de Glushkov
Principaux outils utilisés tableaux, arbres, automates, langages rationnels, expressions rationnelles
Mots clefs expression rationnelle, langage rationnelle, arbre, tableau, Glushkov, automate

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


Épreuve d'informatique 2007 A 2007 INFO. MP ECOLE NATIONALE DES PONTS ET CHAUSSEES, ECOLES NATIONALES SUPÉRIEURES DE L'AÉRONAUTIQUE ET DE L'ESPACE, DE TECHNIQUES AVANCÉES, DES TELECOMMUNICATIONS, DES MINES DE PARIS, DES MINES DE SAINT-ÉTIENNE, DES MINES DE NANCY, DES TELECOMMUNICATIONS DE BRETAGNE, ECOLE POLYTECHNIQUE (FILIÈRE TSI) CONCOURS D'ADMISSION 2007 ÉPREUVE D'INFORMATIQUE Filière MP Durée de l'épreuve : 3 heures. L'usage de calculettes est autorisé. L'utilisation d'un ordinateur est interdite. Sujet mis à disposition des concours : ENSAE (Statistique), ENSTIM, TPE-EIVP, Cycle international 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 12 pages. RECOMMANDATIONS AUX CANDIDATS . 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. 0 Tout résultat fourni dans l'énoncé peut être utilisé pour les questions ultérieures même s'il n'a pas été démontré. . Il ne faut pas hésiter à formuler les commentaires qui semblent pertinents même lorsque l'énoncé ne le demande pas explicitement. COMPOSITION DE L'ÉPREUVE L'épreuve comporte un seul problème, pages 2 à 12. Page 1 sur 12 Tournez la page S.V.P. Épreuve d'informatique 2007 Expressions rationnelles, langages locaux, algorithme de Glushkov Chaque partie du problème peut dépendre des parties précédentes. Les indications données dans une partie sont souvent utiles pour les parties suivantes. Un alphabet 2 est un ensemble fini d'éléments appelés lettres. Un mot sur 2 est une suite finie de lettres de 2 ; la longueur d'un mot est le nombre de lettres le composant ; le mot de longueur nulle est noté 6; une lettre de 2 est aussi un mot de longueur 1. On désigne par E* l'ensemble des mots sur 2, y compris le mot 6. Un langage est une partie de Z*. Soit u = x1x2. . .xp un mot de longueur 19 2 l, avec X,- EUR 2 pour tout i compris entre 1 et p ; xl est la lettre initiale de u et xp est sa lettre finale ; par ailleurs, si i et j sont deux entiers vérifiant lSiSjSp, le motv=xîxi+l...xj estun facteur de M. La concaténation de deux langages L1 et L2 est notée L1.L2. L'intersection de deux langages L1 et L2 est notée L1 0 L2. L'union de deux langages L1 et L2 est notée L1 U L2. Le complémentaire d'un langage L par rapport à Z* est notée L. La différence ensembliste est notée avec le signe '--'. Le cardinal d'un ensemble E quelconque est noté lE |. On suppose dans tout le problème que l'alphabet 2 ne contient aucun des sept symboles ci-dessous : l*l+|- l(l)l®lel Préliminaire concernant la programmation : il faudra écrire des fonctions ou des procédures à l'aide d'un langage de programmation qui pourra être soit Caml, soit Pascal, tout autre langage étant exclu. Indiquer en début de problème le langage de programmation choisi ; il est interdit de modifier ce choix au cours de l'épreuve. Certaines questions du problème sont formulées différemment selon le langage de programmation ; cela est indiqué chaque fois que cela est nécessaire. Lorsque le candidat écrira une fonction ou une procédure, il pourra faire appel à une autre fonction ou procédure définie dans les questions précédentes. Enfin, si les paramètres d'une fonction ou d'une procédure à écrire sont supposés vérifier certaines hypothèses, il ne sera pas utile dans l'écriture de cette fonction ou de cette procédure de tester si les hypothèses sont bien vérifiées. Dans l'énoncé du problème, 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 une police (en italique ; par exemple a) et du point de vue informatique pour l'autre (en romain ; par exemple a). Première partie : expressions rationnelles On appelle expression rationnelle sur l'alphabet 2 toute formule obtenue récursivement à partir des règles suivantes : 0 ® et 6 sont des expressions rationnelles ; 0 pour tout a dans E, a est une expression rationnelle ; 0 si 6 et f sont des expressions rationnelles, (e + f), (6. f ) et (e)* sont des expressions rationnelles (les caractères d'espacement dans ces expressions sont facultatifs et seront ignorés). ATTENTION: Dans ce problème, on ne fera jamais de simplification dans l'écriture d'expressions rationnelles. Une expression rationnelle simplifiée ne sera pas considérée comme étant une expression rationnelle. La longueur d'une expression rationnelle est son nombre total de caractères (lettres de l'alphabet 2 ou symboles "'", '+', '.', '(', ')', '®', '£'). Par exemple, la longueur de l'expression (((a.c))* + 19), où a, b et c appartiennent à l'alphabet, vaut 12. On fait correspondre à chaque expression rationnelle sur l'alphabet 2 un langage dit rationnel sur l'alphabet 2 ; ce langage sera dit décrit par l'expression rationnelle. On rappelle que : . l'expression @ décrit le langage vide ; . l'expression £décrit le langage qui ne contient que le mot 6, 0 si a est dans E, l'expression a décrit le langage réduit au mot a, 0 si el décrit un langage L1 et si 62 décrit un langage L2, (el + 62) décrit le langage L1 U L2 et (61.62) décrit le langage L1.L2, Page 2 sur 12 Épreuve d'informatique 2007 . si e décrit un langage L, (e)"< décrit l'itération, ou étoile, de L, notée L*, c'est-à--dire l'union de toutes les puissances deL : L"< = ULP , avec L0 = {EUR}, L1=L et, pourp 2 2, Lp =L. Lp_ 1. p 2 0 Deux expressions rationnelles sont dites équivalentes si elles décrivent le même langage. Un langage est rationnel si et seulement s'il existe un automate qui le reconnaît. On veut d'abord montrer la propriété (P) suivante : toute expression rationnelle e est équivalente soit à l'expression rationnelle @, soit à l'expression rationnelle EUR, soit a une expression rationnelle e' qui ne contient pas les symboles @ et EUR, soit a une expression rationnelle de la forme (e' + 8), où e' est une expression rationnelle qui ne contient pas les symboles @ et 6. Cl 1 -- Soient e] et e2 deux expressions rationnelles ne contenant pas les symboles @ et EUR; en exhibant sans démonstration des expressions rationnelles équivalentes, montrer que la propriété (P) est exacte pour les huit expressions suivantes : (8+ 8), (el + ®), (6. ®), (el. ®), (el. 8), ((e] + EUR) + (eZ + EUR)), (el .(e2 + EUR)), ((e] + EUR) .(e2 + EUR)). Cl 2 -- Esquisser une démonstration par récurrence de la propriété (P) dans le cas général. En particulier, on fera apparaître les différents cas. ATTENTION : dans toute la suite du problème, on ne considère que des expressions rationnelles ne contenant ni le symbole @, ni le symbole 8, même si cela n'est pas rappelé. On appelle expression sur 2 une suite composée des symboles ""', '+', '.', '(', ')' et de lettres de l'alphabet 2. Une expression n'est pas nécessairement rationnelle ; par exemple, l'expression (a + 19 n'est pas rationnelle alors que l'expression (a + b) l'est; l'expression (a.b)* n'est pas rationnelle alors que l'expression ((a.b))* l'est ; l'expression (a + b).(a. 19) n'est pas rationnelle alors que l'expression ((a + b). (a. b)) l'est. Les expressions rationnelles seront codées par des tableaux indicés a partir de 0 et contenant des entiers de signes quelconques de la façon suivante. On associe des constantes entières négatives distinctes aux cinq symboles utilisés; plus précisément, on associe : 0 une constante nommée ETOILE au symbole '*' avec ETOILE = --1, une constante nommée PLUS au symbole '+' avec PLUS = --2, une constante nommée POINT au symbole '.' avec POINT = --3, une constante nommée P_O au symbole '(' avec P_O = --4, une constante nommée P_F au symbole ')' avec P_F = --5. Dans tout le probléme, ces constantes seront manipulées par leur nom et non par leur valeur. Par ailleurs, les lettres de l'alphabet 2 sont numérotées a partir de 0 ; par exemple, si 2 = {a, b, e}, la lettre 'a' est numérotée 0, la lettre 'b' est numérotée 1 et la lettre 'C' est numérotée 2. En ce sens, l'alphabet est considéré comme ordonné. L'expression rationnelle est alors codée par un tableau obtenu en remplaçant les symboles par les constantes associées et les lettres de l'alphabet 2 par leur numéro. Voici deux exemples pour 2 = {a, b, 6}. Exemple 1 : l'expression rationnelle expression] = (((a.e))* + b) est codée par le tableau exprl ci-dessous : O 1 2 3 4 5 6 7 8 9 10 11 P_O P_O P_O 0 POINT 2 P_F P_F ETOILE PLUS 1 P_F Exemple 2: l'expression rationnelle expression2 = ((b)*.(a + ((a)*.b))) est codée par le tableau expr2 ci-dessous : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 P_O P_O 1 P_F ETOILE POINT P_O 0 PLUS P_O P_O 0 P_F ETOILE POINT 1 P_F P_F P_F Page 3 sur 12 Tournez la page S.V.P. Épreuve d'informatique 2007 Une partie d'un tableau peut aussi coder une expression rationnelle ; c'est le cas par exemple de la partie du tableau exprl située de l'indice 2 inclus à l'indice 6 inclus qui code l'expression rationnelle (a.c). Quand on dira simplement qu'un tableau code une expression rationnelle, cette expression rationnelle sera celle qui est codée a partir de l'indice 0 du tableau. Premières indications pour la programmation Caml On définit des constantes par les instructions ci-dessous : let ETOILE = --l;; let PLUS = --2;; let POINT = --3;; let P_O = --4;; let P_F = --5;; Les expressions sont codées dans des tableaux ayant un nombre de cases exactement égal à la longueur de l'expression. Si un tableau expr code une expression, vect_length expr donne la longueur de l'expression. Fin des premières indications pour Caml Pascal Dans tout le problème, on suppose qu'on écrit les différentes fonctions ou procédures dans un fichier contenant les définitions suivantes : const MAX = 100; ETOILE = --1; PLUS = --2; POINT = --3; P_O = --4; P_F = --5; type Table_Integer = array[0 .. MAX -- 1] of Integer; type Table_Boolean = array[0 .. MAX -- 1] of Boolean; type Matrice_Boolean = array[0 .. MAX -- l, 0 .. MAX -- 1] of Boolean; Les expressions sont codées dans des tableaux de type Table_Integer a partir de l'indice 0. On suppose que toutes les expressions traitées ont une longueur inférieure ou égale àla constante MAX ; on suppose aussi que l'alphabet n'a pas plus de MAX lettres. Fin des premières indications pour Pascal [| 3 -- Écrire dans le langage de programmation choisi une fonction nommée est_symbole prenant un paramètre entier et qui renvoie une valeur booléenne indiquant si l'entier reçu en paramètre a ou non une valeur égale à l'une des cinq constantes ETOILE, PLUS, POINT, P_O, P_F. Cl 4 -- On considère un tableau expr codant une expression de longueur EUR 2 l et deux indices notés debut et fin vérifiant 0 S debut < fin < 5. Il s'agit d'écrire en langage de programmation une fonction à valeurs entières nommée cesure qui prend debut et fin comme paramètres et qui cherche s'il existe un indice i vérifiant simultanément : ° debut < i'PEUR FGUille @ dEUR typEUR FGUille Page 5 sur 12 Tournez la page S.V.P. Épreuve d'informatique 2007 Pascal En plus des définitions indiquées plus haut, on définit les types suivants : type Arbre = ANoeud; Noeud = record num : Integer; filsl, filsZ: Arbre; end; Une variable de type Noeud est un enregistrement. Un enregistrement contient des champs (aussi appelés des membres) ; par exemple, ici, une variable de type Noeud contient les champs num, f ilsl, f ilsZ . Une variable A de type Arbre est appelée pointeur vers une variable de type Noeud ; la variable A permet de créer une variable de type Noeud pendant l'exécution du programme ; cela se fait en invoquant new (A) . L'enregistrement créé est dit pointé par A et se note AA ; les champs de cet enregistrement sont accessibles en faisant suivre AA d'un point puis du nom du champ considéré, comme cela est fait un peu plus bas. Lorsqu'un arbre est construit pour représenter une expression rationnelle, il faut créer un enregistrement de type Noeud pour chacun des noeuds de l'arbre. Cela se fait en utilisant les trois fonctions ci-dessous. La fonction nouvelle_feuille permet de créer une feuille contenant la valeur de l'entier reçu en paramètre ; on donne aux champs f ilsl et f ilsZ la valeur nil, ce qui signifie que le noeud créé n'a ni fils gauche, ni fils droit. function nouvelle_feuille(numero : Integer) : Arbre; var A : Arbre; begin new(A); AA.num := numero; AA.filsl := nil; AA.filSZ := nil; nouvelle_feuille := A; end; La fonction nouvel_unaire permet de créer un noeud interne ayant un seul fils qui est le fils gauche. Elle correspond à l'opérateur "'" appliqué à l'expression rationnelle représentée par le sous--arbre fils reçu en paramètre ; on donne au champ f ilsZ la valeur nil, ce qui signifie qu'il n'y a pas de fils droit. function nouvel_unaire(fils : Arbre) : Arbre; var A : Arbre; begin new(A); AA.num := ETOILE; AA.filsl := fils; AA.filSZ := nil; nouvel_unaire := A; end; La fonction nouveau_binaire permet de créer un noeud interne ayant deux fils. Elle correspond aux opérateurs '+' ou '.' appliqués aux expressions rationnelles représentées par les sous-arbres f ilsl et f ilsZ reçus en paramètres ; le paramètre numero vaudra selon le cas la valeur PLUS ou la valeur POINT. function nouveau_binaire(numero : Integer; filsl, filsZ : Arbre) : Arbre; var A : Arbre; begin new(A); AA.num := numero; AA.filsl := filsl; AA.filSZ := filsZ; nouveau_binaire := A; end; Page 6 sur 12 Épreuve d'informatique 2007 L'expression expression] = (((a.e))* + b) est décrite en Pascal par l'arbre représenté ci-contre ; @ - les cases vides contiennent la valeur nil. " " Fin des indications pour Pascal [| 7 -- Il s'agit d'écrire une fonction nommée exp re s s ion_vers_a rbre qui permette de construire un arbre représentant une expression rationnelle. Caml : écrire en Caml une fonction récursive expression_vers_arbre telle que : 0 si expr est un tableau codant une expression rationnelle e de longueur EUR 2 l, 0 si debut et fin sont deux entiers vérifiant 0 S debut 5 fin < EUR pour lesquels la partie du tableau expr située entre l'indice debut inclus et l'indice fin inclus code une expression rationnelle notée e', alors expression_vers_arbre debut fin renvoie une valeur de type Arbre donnant la racine d'un arbre qui représente l'expression e'. Pascal : écrire en Pascal une fonction récursive expression_vers_arbre telle que : 0 si expr est de type Table_Integer et code une expression rationnelle e de longueur EUR 2 l, 0 si debut et fin sont deux entiers vérifiant 0 S debut 5 fin < EUR pour lesquels la partie du tableau expr située entre l'indice debut inclus et l'indice fin inclus code une expression rationnelle notée e', alors expression_vers_arbre (debut , fin) renvoie une valeur de type Arbre donnant la racine d'un arbre qui représente l'expression e'. [| 8 -- Il s'agit d'écrire en langage de programmation une fonction nommée eontient_epsilon permettant de tester si le langage décrit par une expression rationnelle contient ou non le mot 6. Ce test est fait a partir de l'arbre représentant l'expression rationnelle. Caml : écrire en Caml une fonction récursive contient_epsilon telle que : 0 si arbre est de type Arbre et représente une expression rationnelle e, alors contient_epsilon arbre renvoie une valeur booléenne indiquant si le langage décrit par e contient ou non le mot 6. Pascal : écrire en Pascal une fonction récursive contient_epsilon telle que : 0 si A est de type Arbre et représente une expression rationnelle e, alors contient_epsilon (A) renvoie une valeur booléenne indiquant si le langage décrit par e contient ou non le mot 6. Deuxième partie : langages locaux On note 22 l'ensemble des mots de longueur 2 sur un alphabet 2. On dit qu'un langage L sur un alphabet 2 est un langage local s'il existe simultanément : 0 un sous-ensemble ] de Z, 0 un sous-ensemble F de Z, 0 un sous-ensemble P de 22 tels qu'un mot u de 2* autre que le mot 6 appartienne a L si et seulement si : Page 7 sur 12 Tournez la page S.V.P. Épreuve d'informatique 2007 . la lettre initiale de u est dans [, 0 la lettre finale de u est dans F, 0 si la longueur de u est au moins 2, tout facteur de longueur 2 de u est dans P. Un langage local L peut contenir ou non le mot 6. Un mot de longueur 1 appartient a un langage local si la lettre qui le compose est a la fois dans I et dans F. On peut ainsi définir un langage local L par l'ensemble 1 des lettres initiales permises, l'ensemble F des lettres finales permises, l'ensemble P des facteurs de longueur 2 permis et le fait de contenir ou non le mot 6. En posant a= vrai si L contient 6 et a = faux si L ne le contient pas, on dit alors dans ce problème que le langage local L est caractérisé par le quadruplet (I, F, P, a). Les ensembles ], F et P peuvent être vides. Si 1 est vide, le langage L est alors soit vide, soit réduit au mot 6; il en est de même si F est vide. Cl 9 -- On considère l'alphabet 2 = {a, 19}. Montrer que les langages décrits par les expressions rationnelles (a.(a)*) et ((a.b))* sont locaux. On donnera pour chacun des langages un quadruplet qui le caractérise. Cl 10 -- Déterminer celles des propositions ci-dessous qui sont exactes. Dans chaque cas, on indiquera clairement la réponse et on justifiera celle--ci. . Proposition sur l'union : l'union de deux langages locaux est un langage local. 0 Proposition sur l'intersection : l'intersection de deux langages locaux est un langage local. 0 Proposition sur la concaténation : la concaténation de deux langages locaux est un langage local. 0 Proposition sur l'ite'ration : l'itération L * d'un langage local L est un langage local. [| 11 -- Soit L un langage défini sur l'alphabet 2. On suppose que L est local et caractérisé par le quadruplet (I, F, P, a). Exprimer a l'aide des langages [, F, P, Z, Z* et en utilisant uniquement les opérations d'intersection, de concaténation et de complémentation par rapport a Z* : ° le langage des mots dont la lettre initiale est dans I, le langage des mots dont la lettre finale est dans F, le langage des mots de longueur 2 qui ne sont pas dans P, puis le langage des mots contenant au moins un facteur de longueur 2 qui n'est pas dans P, puis le langage L -- {6}. Cl 12 -- Déduire de la question précédente qu'un langage local est un langage rationnel. Un sous-ensemble E de lettres de l'alphabet 2 est représenté à l'aide d'un tableau de valeurs booléennes ; pour i compris entre 0 et |El -- 1, la case d'indice i du tableau contient la valeur vrai si la lettre de numéro i appartient a E et la valeur faux sinon. Par exemple, le sous-ensemble {a, e} de 0 1 2 3 l'alphabet 2 = {a, b, e, d} est codé par le tableau : vrai faux vrai faux Un ensemble P de mots de longueur 2 sur l'alphabet 2 est représenté à l'aide d'une matrice de valeurs booléennes ; pour i compris entre 0 et |El -- 1 et pour j compris entre 0 et |Z| -- 1, la case de ligne i et de colonne j de la matrice contient la valeur vrai si le mot de longueur 2 composé de la lettre de numéro i suivie de la lettre de numéro j appartient à P (on dit alors que cette case correspond au mot considéré) et la valeur faux sinon. Par exemple, l'ensemble de mots {ae, be, ed, 1919, ad, 0 1 2 3 db, ca} sur l'alphabet 2 = {a, b, e, d} est codé par la 0 faux faux vrai vrai matrice ci-contre. Dans cette matrice, la case d'indices 1 1 faux vrai vrai faux et 2 correspond au mot be. 2 vrai faux faux vrai 3 faux vrai faux faux Les mots sont codés par un tableau d'entiers donnant les indices de leurs lettres successives dans l'alphabet Z. Par exemple, le mot aebba sur l'alphabet 2 = {a, b, e} est codé par le tableau : 0 1 2 3 4 0 2 1 1 0 Page 8 sur 12 Épreuve d'informatique 2007 [| 13 -- Il s'agit de définir une fonction nommée appartient déterminant si un mot sur 2 autre que 6 appartient ou non au langage local caractérisé par le quadruplet (I, F, P, a). Caml : écrire en Caml une fonction nommée appartient telle que : 0 si mot est un tableau de longueur EUR codant un mot u sur 2 autre que Set de longueur EUR 2 1, 0 si I et F sont deux tableaux de longueur |Zl codant des sous--ensembles ] et F de 2, 0 si P est une matrice carrée dont les deux dimensions valent |Z| et qui code un ensemble P de mots de longueur 2 sur 2, alors appartient mot I F F renvoie une valeur booléenne indiquant si le mot u appartient ou non au langage local caractérisé par le quadruplet (I, F, P, 05). Pascal : écrire en Pascal une fonction nommée appartient telle que : 0 si mot est de type Table_Integer et contient le code d'un mot u sur 2 autre que 6, 0 si longueur est un entier ayant pour valeur la longueur de u, 0 si I et F sont de type Table_Boolean et codent des sous--ensembles ] et F de 2, 0 si P est de type Mat rice_Boolean et code un ensemble P de mots de longueur 2 sur 2, alors appartient (mot, longueur, I , F, F) renvoie une valeur booléenne indiquant si le mot u appartient ou non au langage local caractérisé par le quadruplet (I, F, P, a). Troisième partie : mots appartenant au langage décrit par une expression rationnelle [| 14 -- On considère une expression rationnelle e sur un alphabet 2 dans laquelle toute lettre de 2 figure au plus une fois, c'est-à--dire dans laquelle toutes les lettres sont distinctes. Montrer que le langage L décrit par e est un langage local. Soit e une expression rationnelle et soit L le langage décrit par e. On note [(e) l'ensemble des lettres initiales des mots de L, F (e) l'ensemble des lettres finales des mots de L, P(e) l'ensemble des facteurs de longueur 2 des mots de L et Ode) la valeur vrai ou faux selon que L contient ou non le mot 6. Cl 15 -- On rappelle qu'on a défini: expression] = (((a.e))* + b). Indiquer sans démonstration les valeurs de I(expressi0nl ), F (expressionl ), P(expressi0nl ) et OE(expressionl ). Cl 16 -- Étant donnée une expression rationnelle e sur un alphabet 2 , il s'agit d'écrire en langage de programmation une fonction ou une procédure nommée calcul_I qui permette de déterminer l'ensemble I(e). Caml : écrire en Caml une fonction récursive calcul_I telle que : 0 si arbre est de type Arbre et représente une expression rationnelle e sur un alphabet 2 comme cela a été décrit avant la question Cl 7, 0 si I est un tableau de longueur |El destiné a coder un sous-ensemble de 2 de la manière expliquée avant la question [| 13, alors calcul_I arbre I modifie le tableau I en affectant la valeur true aux cases dont l'indice est égal au numéro d'une lettre de [(e) (la fonction ne modifie pas les autres cases de I). Remarque : on suppose qu'avant le premier appel de la fonction calcul_I, un tableau de variables booléennes a été créé et initialisé en attribuant à toutes les cases la valeur false ; c'est ce tableau qui contiendra a la fin la description de l'ensemble 1 ; cette initialisation n'est pas à écrire. Pascal : écrire en Pascal une procédure récursive calcul_I telle que : 0 si A est de type Arbre et représente une expression rationnelle e sur un alphabet 2 comme cela a été décrit avant la question Cl 7, 0 si I est de type Table_Boolean et est destiné a coder un sous-ensemble de 2 de la manière expliquée avant la question Cl 13, alors calcul_I (A, I) modifie le tableau I en affectant la valeur true aux cases dont l'indice est égal au numéro d'une lettre de [(e) (la procédure ne modifie pas les autres cases de I). Page 9 sur 12 Tournez la page S.V.P. Épreuve d'informatique 2007 Remarque : on suppose qu'avant le premier appel de la procédure calcul_T, un tableau de variables booléennes a été défini et initialisé en attribuant à toutes les cases la valeur false ; c'est ce tableau qui contiendra a la fin la description de l'ensemble 1 ; cette initialisation n'est pas à écrire. Étant donnée une expression rationnelle e sur un alphabet 2 , on admet qu'on peut écrire en langage de programmation une fonction ou une procédure nommée calcul_F qui permette de déterminer l'ensemble F (6) en codant le tableau représentant F (6) de manière analogue à ce qui a été fait pour I(e). Cette fonction ou cette procédure aurait les mêmes types de paramètres que la fonction ou la procédure calcul_I. On ne demande pas d'écrire la fonction ou la procédure calcul_F mais on pourra y faire appel dans la suite du problème. Cl 17 --Il s'agit d'écrire une fonction ou une procédure qui servira pour le calcul ultérieur de l'ensemble P(e). Caml : écrire en Caml une fonction nommée ajout_couples telle que : 0 si produit est une matrice carrée de booléens de dimension dim >< dim, 0 si T1 et T2 sont deux tableaux de booléens de dimension dim, alors ajout_couples produit T1 T2 modifie la matrice produit en affectant, pour tout i et tout j vérifiant 0 S i < dim et 0 5 j < dim, la valeur true a la case d'indices i et j si les cases d'indice i du tableau T1 et d'indice j du tableau T2 contiennent toutes deux la valeur true (la fonction ne modifie pas les autres cases de la matrice). Pascal : écrire en Pascal une procédure nommée ajout_couples telle que : 0 si produit est de type Matrice_Boolean, . si T1 et T2 sont de type Table_Boolean, . si dim est un entier, alors ajout_couples (produit, T1, T2, dim) modifie la matrice produit en affectant, pour tout i et tout j vérifiant 0 S i < dim et 0 5 j < dim, la valeur true a la case d'indices i et j si les cases d'indice i du tableau T1 et d'indice j du tableau T2 contiennent toutes deux la valeur true (la procédure ne modifie pas les autres cases de la matrice). Cl 18 -- Étant donnée une expression rationnelle e sur un alphabet 2 , il s'agit d'écrire en langage de programmation une fonction ou une procédure nommée calcul_P qui permette de déterminer l'ensemble P(e). Caml : écrire en Caml une fonction récursive calcul_P telle que : 0 si arbre est de type Arbre et représente une expression rationnelle e sur un alphabet Z, 0 si P est une matrice carrée dont les deux dimensions valent |Z| et qui est destinée à coder un ensemble de mots de longueur 2 sur 2 comme expliqué avant la question Cl 13, alors calcul_P arbre P modifie le tableau P en affectant la valeur true aux cases correspondant aux éléments de P(e) (la fonction ne modifie pas les autres cases de la matrice). Pascal : écrire en Pascal une procédure récursive calcul_P telle que : 0 si A est de type Arbre et représente une expression rationnelle e sur un alphabet Z, 0 si P est de type Mat rice_Boolean et est destiné a coder un ensemble de mots de longueur 2 sur 2 de la manière expliquée avant la question Cl 13, alors calcul_P A P modifie le tableau P en affectant la valeur true aux cases correspondant aux éléments de P(e) (la procédure ne modifie pas les autres cases de la matrice). [| 19 -- On considère une expression rationnelle e sur un alphabet 2 dans laquelle toutes les lettres sont distinctes; on note L le langage décrit par EUR. Soit u un mot sur 2 autre que 6. Décrire un algorithme utilisant les fonctions ou procédures écrites précédemment pour déterminer si le mot u appartient ou non a L. Cl 20 -- On considère une expression rationnelle e sur un alphabet 2 ; il s'agit d'écrire en langage de programmation une fonction nommée lettres_distinctes qui permette de déterminer si toutes les lettres de 6 sont distinctes, c'est-à--dire si toute lettre de 2 figure au plus une fois dans 6. Page 10 sur 12 Épreuve d'informatique 2007 Caml : écrire en Caml une fonction lett re s_di st inctes telle que, 0 si expr est un tableau codant une expression e sur un alphabet Z, 0 si n est un entier qui donne le cardinal de l'alphabet 2, alors lett re s_dist inctes expr n renvoie une valeur booléenne indiquant si les lettres de l'expression e sont ou non distinctes. Pascal : écrire en Pascal une fonction lett re s_di st inctes telle que, 0 si expr est de type Table_Integer et code une expression rationnelle e sur un alphabet Z, 0 si longueur est un entier qui donne la longueur de l'expression e, 0 si n est un entier qui donne le cardinal de l'alphabet 2, alors lett res_di st inctes (expr, longueur, n) renvoie une valeur booléenne indiquant si les lettres de l'expression e sont ou non distinctes. On considère une expression rationnelle e sur un alphabet 2. On traduit cette expression en une autre expression rationnelle e' en utilisant un second alphabet 2 ' de cardinal aussi grand que nécessaire. Pour cela, on traduit le codage de e en le codage de e' de la manière suivante. Les lettres de l'alphabet 2 ' sont numérotées par 0, 1, 2. .. comme cela est fait pour l'alphabet 2. Pour passer du codage de e au codage de e', toutes les valeurs représentant les symboles de e sont recopiées a la même place dans le codage de e'. Les numéros des lettres du codage de e sont remplacés dans le codage de e' de la gauche vers la droite successivement par 0, 1, 2, 3, etc. Par exemple, l'expression rationnelle expression2 = ((b)*.(a + ((a)*.b))) sur l'alphabet 2 = {a, b} est transformée en l'expression rationnelle expression? sur 2 'dont le codage est le tableau ci-dessous : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 P_O P_O 0 P_F ETOILE POINT P_O 1 PLUS P_O P_O 2 P_F ETOILE POINT 3 P_F P_F P_F En supposant que l'alphabet E' est l'ensemble ordonné {A, B, C, D, ...}, expression2 est donc traduite en expressi0n2' = ((A)*.(B + ((C)*.D))). Soit q le nombre de lettres intervenant dans l'expression rationnelle e, distinctes ou non. Par exemple, si e est expressi0n2, le nombre q vaut 4. On définit une application a) des q premières lettres de 2 ' dans les lettres de 2 ; si une occurrence de la lettre x se trouvant dans e a été remplacée dans e' par une lettre y, on pose $(y) = x. Si e est expression2, on a ainsi $(A) = b, $(B) = a, $(C) = a, $(D) = 19. Soit u = x1x2. . .Je]; un mot sur l'alphabet 2. Avec les notations précédentes, on admet l'équivalence suivante : « le mot a appartient au langage décrit par e si et seulement s'il existe un mot y1y2. . . yp appartenant au langage décrit par e' et vérifiant, pour i compris entre 1 et p, $(yi) = xl-- ». Cl 21 -- Soient e une expression rationnelle sur un alphabet 2 et L le langage décrit par e. Décrire sommairement un algorithme qui permette de déterminer si un mot a sur 2 autre que 6 appartient ou non a L. Quatrième partie : algorithme de Glushkov Cette dernière partie a pour objectif de décrire l'algorithme de Glushkov ; cet algorithme permet de construire un automate fini qui reconnaît le langage décrit par une expression rationnelle. Les rappels de définitions qui suivent permettent de fixer la terminologie et les notations. Un automate fini 54 est décrit par une structure , où : ° 2 est un alphabet ; 0 Q est un ensemble fini et non vide appelé ensemble des états de 54 ; 0 T ç Q >< 2 >< Q est appelé l'ensemble des transitions ; étant donnée une transition (p, a, a) E T, on dit a qu'elle va de l'état p vers l'état q et qu'elle est d'étiquette a ; on pourra la noter p % q ; 0 I g Q est appelé ensemble des états initiaux de 521; ° F g Q est appelé ensemble des états finals de flL Page 11 sur 12 Tournez la page S.V.P. Épreuve d'informatique 2007 [| 22 -- On considère le langage local L1 sur l'alphabet 2 = {a, b, 6} caractérisé par le quadruplet (11, F1, P1, al) avec: ' Ï1={a} ; ' F1= {C} ; 0 P1 = {ah, bc, ca} ; ° a1=faux. Dessiner sans démonstration un automate déterministe 541 possédant quatre états et reconnaissant le langage L1. [| 23 -- On considère le langage local L2 sur l'alphabet 2 = {a, b, 6} caractérisé par le quadruplet (12, F2, P2, az) avec : ' Ï2 : {"; C} ; ' F 2 = {19} ; 0 P2 = {ah, ac, ba, cb, cc} ; ° 052 = vraz. Dessiner sans démonstration un automate déterministe 5212 possédant quatre états et reconnaissant le langage L2 ; l'automate 5212 doit être tel qu'aucune transition ne va vers l'état initial et que toutes les transitions allant vers un même état q portent la même étiquette ; a part l'état initial, il doit y avoir un état par lettre de l'alphabet. Cl 24 -- Soit L un langage sur l'alphabet 2. On suppose que L est un langage local caractérisé par un quadruplet (I, F , P, a). Décrire un automate f£l déterministe qui reconnaisse le langage L et ayant |Z | + 1 états. On ne demande pas de justifier la construction. Cl 25 -- On considère une expression rationnelle e sur un alphabet 2. On note L le langage décrit par EUR. En utilisant ce qui a été fait précédemment, en particulier la transformation de e en une expression e' où toutes les lettres sont distinctes et la construction d'un automate reconnaissant un langage local, décrire un algorithme permettant de construire un automate reconnaissant L. On montrera que l'automate obtenu reconnait le langage L. [| 26 -- Appliquer l'algorithme de la question précédente à expression2 = ((b)*.(a + ((a)*.b))) pour construire un automate reconnaissant le langage décrit par cette expression. On traduira expression2 en une expression expressi0n2' en utilisant un alphabet E' = {A, B, C, D, ...} comme il a été fait dans les indications précédant la question Cl 21. On donnera sans démonstration les ensembles I(expressi0n2 '), F (expressi0n2 '), P(expression2fi et la valeur de a(expressi0n2 '). Cl 27 -- Utiliser une méthode au choix pour transformer l'automate obtenu à la question précédente en un automate déterministe équivalent. On se contentera de dessiner l'automate obtenu en indiquant sur la figure à quoi correspondent les nouveaux états. Page 12 sur 12

Extrait du corrigé obtenu par reconnaissance optique des caractères


 Mines Informatique MP 2007 -- Corrigé Ce corrigé est proposé par Sattisvar Tandabany (ENS Lyon) ; il a été relu par Samuel Mimram (ENS Lyon) et Vincent Puyhaubert (Professeur en CPGE). Ce sujet est un long problème qui s'articule en quatre parties dépendant les unes des autres. · La première partie définit les expressions rationnelles avec une écriture totalement parenthésée. L'implémentation des expressions rationnelles utilisées ici fait intervenir dans un premier temps des tableaux d'entiers, chaque symbole étant associé à un entier. Puis, une structure d'arbre est décrite pour représenter les expressions rationnelles. Cette partie consiste surtout à rédiger des programmes pour manipuler les tableaux codant des expressions rationnelles, et à transformer un tableau en arbre. · La deuxième partie est consacrée aux langages que décrivent les expressions rationnelles. L'accent est mis sur une classe particulière de langages, dits locaux. Cette partie, plus algorithmique, nécessite de manipuler ces langages afin de démontrer des propriétés utiles par la suite. · La troisième partie revient sur un peu plus de programmation. Une caractérisation des langages locaux est mise en oeuvre. · La quatrième partie traite de l'algorithme de Glushkov, permettant de construire un automate capable de reconnaître le langage décrit par une expression rationnelle. Il est demandé de dessiner quelques automates ; les indications de l'énoncé sont amplement suffisantes pour réussir cette partie. L'ensemble du problème constitue une bonne révision des langages rationnels mais requiert une dextérité certaine dans la programmation, qui implique de réviser l'utilisation de tableaux et d'arbres. L'énoncé rappelle que des indications données dans une partie peuvent s'avérer utiles dans les parties suivantes (et même parfois dans celles qui précèdent). C'est pourquoi il est vivement conseillé de lire l'ensemble de l'énoncé dès le début. Indications Première partie 3 Écrire la disjonction de cas. 4 Utiliser un compteur qui tient à jour le nombre de parenthèses ouvrantes non encore refermées. 5 Distinguer les cas selon la valeur de la case d'indice debut et celle de la case d'indice fin. 6 L'algorithme indique comment répondre pour chacune des structures possibles d'une expression rationnelle. 7 Considérer les même cas qu'à la question 5. 8 Suivre l'algorithme décrit à la question 6. Deuxième partie 10 Étudier l'union de ces deux langages locaux dont on a précisé le quadruplet qui les caractérise : L1 caractérisé par (I1 = {a}, F1 = {b}, P1 = {ab}, 1 = f alse) L2 caractérisé par (I2 = {b}, F2 = {c}, P2 = {bc}, 2 = f alse) Montrer que l'intersection de L1 , langage local caractérisé par (I1 , F1 , P1 , 1 ), et de L2 , langage local caractérisé par (I2 , F2 , P2 , 2 ), est le langage local caractérisé par (I1 I2 , F1 F2 , P1 P2 , 1 2 ). Étudier la concaténation de L1 = {ab} et de L2 = {bc}. Utiliser la caractérisation de l'étoile comme solution de l'équation sur les langages X {} = L.X. 11 Le langage L-{} peut être exprimé à l'aide des autres langages dont on demande l'expression dans cette question. Troisième partie 14 Procéder par récurrence sur la longueur de n. Dans la récurrence, pour le cas de l'étoile, procéder encore par une récurrence sur la taille des mots du langage. 18 L'énoncé permet d'utiliser la fonction calcul_F. Calculer P(e) par induction sur la structure d'arbre de l'expression e. 19 Utiliser la question 13 ainsi que les questions 16 et 18. 20 Utiliser un tableau temporaire pour tenir à jour les lettres rencontrées. Quatrième partie 22 Lire l'indication donnée par l'énoncé pour la question 23. 24 S'inspirer de l'indication de la question 23 pour décrire l'automate général. I. Expressions rationnelles 1 Il convient de distinguer 8 cas. Ci-dessous, nous présentons pour chaque expression demandée, l'expression rationnelle équivalente qui justifie que l'expression rationnelle étudiée vérifie la propriété (P) : 1. ( + ) est équivalente à ; 2. (e1 + ) est équivalente à e1, c'est-à-dire à une expression rationnelle ne contenant pas les symboles et par hypothèse ; 3. (.) est équivalente à ; 4. (e1.) est équivalente à ; 5. (e1.) est équivalente à e1 ; 6. ((e1 + ) + (e2 + )) est équivalente à (e + ), où e est l'expression rationnelle (e1+e2) où ne figurent pas les symboles et , car ni e1 ni e2 ne les contiennent ; 7. (e1.(e2 + )) est équivalente à ((e1.e2) + e1) où ne figurent pas les symboles et , car ni e1 ni e2 ne les contiennent ; 8. ((e1 + ).(e2 + )) est équivalente à (e + ), où e est l'expression rationnelle (((e1.e2) + e1) + e2) où ne figurent pas les symboles et , car ni e1 ni e2 ne les contiennent. 2 Montrons que la propriété P(n), qui stipule que « si e est une expression rationnelle de longueur n, alors e vérifie (P) », est vraie pour tout n > 1. · P(1) est vraie, car une expression rationnelle de longueur 1 est soit , soit , soit une lettre de l'alphabet , et donc ne contient pas et . · ( 1 6 i 6 n, P(i)) = P(n + 1) : soit e une expression rationnelle de longueur n + 1. Comme n + 1 > 1, e n'est ni ni . Si e ne contient ni ni , alors P(n + 1) est vraie. Sinon, trois cas sont possibles : ­ 1er cas : e = (e ) . D'après l'hypothèse de récurrence, e étant une expression rationnelle de longueur inférieure à n, e peut être équivalente à l'une des quatre expressions listées dans la première colonne du tableau ci-dessous. Pour chaque cas, figure dans la deuxième colonne une écriture équivalente de e montrant qu'elle vérifie la propriété (P). e e sans , (e + ) e = (e ) (e ) (e ) ­ 2e cas : e = (e1 + e2 ). D'après l'hypothèse de récurrence, e1 et e2 étant des expressions rationnelles de longueurs inférieures à n, elles peuvent être équivalentes à l'une des quatre expressions listées dans le tableau ci-dessous. Pour chaque cas, figure dans le tableau une écriture équivalente de e montrant qu'elle vérifie la propriété (P). e1 /e2 e1 (e1 + ) e1 (e1 + ) (e1 + ) (e1 + ) e2 e2 (e2 + ) (e1 + e2 ) ((e1 + e2 ) + ) (e2 + ) (e2 + ) (e2 + ) ((e1 + e2 ) + ) ((e1 + e2 ) + ) ­ 3e cas : e = (e1 .e2 ). D'après l'hypothèse de récurrence, e1 et e2 étant des expressions rationnelles de longueurs inférieures à n, elles peuvent être équivalentes à l'une des quatre expressions listées dans un tableau similaire à celui du cas précédent. On obtient cette fois le tableau suivant : e1 /e2 e1 (e1 + ) · Conclusion : e1 (e1 + ) e2 e2 (e1 .e2 ) ((e1 .e2 ) + e2 ) (e2 + ) (e2 + ) ((e1 .e2 ) + e1 ) ((((e1 .e2 ) + e1 ) + e2 ) + ) Pour tout n, P(n) est vraie. Dans la récurrence précédente, il existe des entiers n pour lesquels on ne peut pas trouver d'expression rationnelle de longueur n+1. Par exemple pour n = 1, il n'existe pas d'expression rationnelle de longueur 2, car toute expression rationnelle est, ou bien un symbole unique, ou bien une expression faisant intervenir deux parenthèses et un troisième symbole. Dans ce cas, P(n + 1) est automatiquement vraie, car fondée sur un quantificateur universel dans un ensemble vide. 3 La fonction demandée procède par une disjonction des cas. let est_symbole n = n = ETOILE || n = PLUS || n = POINT || n = P_O || n = P_F;; Les cinq constantes étant choisies à valeur négative, une manière simple de déterminer si le paramètre est un symbole pourrait être de vérifier que l'entier est négatif. Il est cependant préférable de faire intervenir le nom de chacune des constantes pour que le programme soit facilement modifiable, au cas où les valeurs des constantes changeraient. 4 Afin que l'indice i vérifie simultanément les trois conditions, parcourons le tableau à partir de l'indice debut+1, et maintenons à jour un compteur qui donne le nombre de parenthèses ouvrantes rencontrées et qui n'ont pas encore été refermées. Il s'agit simplement d'incrémenter ce compteur lorsqu'on rencontre une parenthèse ouvrante, et de le décrémenter dans le cas d'une parenthèse fermante. Ainsi, lors du parcours du tableau, le plus petit i vérifiant les trois conditions sera l'indice de la première case rencontrée qui contient la valeur PLUS ou la valeur POINT avec le compteur de parenthèses égal à zéro. Si un tel indice n'est pas rencontré, on renvoie -1. let cesure expr debut fin = let cmpt_par = ref 0 in let indice = ref (debut+1) in while !indice < fin && ((expr.(!indice) <> PLUS && expr.(!indice) <> POINT) || !cmpt_par != 0) do if expr.(!indice) = P_O then cmpt_par := !cmpt_par + 1; if expr.(!indice) = P_F then cmpt_par := !cmpt_par - 1; indice := !indice + 1; done; if !indice = fin then -1 else !indice;;