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;;