Mines Informatique MP 2007

É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