Mines Informatique optionnelle MP 2015

Thème de l'épreuve Automates d'arbres
Principaux outils utilisés listes, automates, langages
Mots clefs arbres, impartial, automate d'arbre

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


A2015INFO.MP
École des Ponts ParisTech,
SUPAERO (ISAE), ENSTA ParisTech,
Télécom ParisTech, Mines ParisTech,
Mines de Saint-étienne, Mines Nancy,
Télécom Bretagne, ENSAE ParisTech (filière MP),
École polytechnique (filière TSI)
Concours 2015

Épreuve d'Informatique
Filière : MP
Durée de l'épreuve : 3 heures.
L'utilisation d'une calculatrice est autorisée.
Sujet mis à la disposition des concours :
Cycle international, Écoles des Mines, Télécom Sud Paris, TPE-EIVP.

L'énoncé de cette épreuve comporte 10 pages.
Les candidats sont priés de mentionner de façon apparente
sur la première page de la copie :
INFORMATIQUE ­ MP
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.
-- 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 unique problème (pages 2 à 10), comportant 32 questions.

Page 1 sur 10

Épreuve d'informatique 2015

Problème : Automates d'arbre
Préliminaire concernant la programmation
Il faudra coder des fonctions à l'aide du langage de programmation Caml, tout 
autre
langage étant exclu. Lorsque le candidat écrira une fonction, il pourra faire 
appel à d'autres
fonctions définies dans les questions précédentes ; il pourra aussi définir des 
fonctions
auxiliaires. Quand l'énoncé demande de coder une fonction, il n'est pas 
nécessaire de
justifier que celle-ci est correcte, sauf si l'énoncé le demande explicitement. 
Enfin, si les
paramètres d'une fonction à coder sont supposés vérifier certaines hypothèses, 
il ne sera
pas utile dans l'écriture de cette fonction de tester si les hypothèses sont 
bien vérifiées.
Dans les énoncés 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 la police en italique (par exemple n) et du point de vue informatique pour 
celle en
romain avec espacement fixe (par exemple n).

Fonctions utilitaires
Dans cette partie, on code quelques fonctions générales qui seront utiles par 
la suite.
On ne cherchera pas à proposer l'implémentation la plus efficace possible de 
chaque
fonction.
Quand il est question de donner la complexité d'une fonction, il s'agit de 
calculer la
complexité asymptotique en temps, en notation O(·), de cette fonction dans le 
pire des
cas. Il est inutile de donner une preuve de cette complexité.
1 ­ Coder une fonction Caml contient: 'a list -> 'a -> bool telle que
contient li x renvoie un booléen qui vaut Vrai si et seulement si la liste li
contient l'élément x. Donner la complexité de cette fonction.
2 ­ En utilisant la fonction contient, coder une fonction Caml union:
'a list -> 'a list -> 'a list telle que union l1 l2, où l1 et l2 sont deux
listes d'éléments sans doublon dans un ordre arbitraire, renvoie une liste
sans doublon contenant l'union des éléments des deux listes, dans un ordre
arbitraire. Donner la complexité de cette fonction.
3 ­ En utilisant la fonction union, coder une fonction Caml fusion:
'a list list -> 'a list telle que fusion l, où l est une liste de listes
d'éléments, chacune de ces listes étant sans doublon, renvoie une liste de tous
les éléments contenus dans au moins une des listes de la liste l, sans doublon
et dans un ordre arbitraire. En notant l = (l1 , . . . , lk ) la liste codée 
par l
P
et en posant L := kj=1 |lj |, donner la complexité de la fonction fusion en
fonction de L.

Page 2 sur 10

Épreuve d'informatique 2015
4 ­ Coder produit: 'a list -> 'b list -> ('a * 'b) list, telle que
produit l1 l2 renvoie une liste de tous les couples (x,y) avec x un élément
de l1 et y un élément de l2. On supposera les listes l1 et l2 sans doublon.
La liste résultante doit avoir pour longueur le produit des longueurs des deux
listes. Donner la complexité de cette fonction.

Arbres binaires étiquetés
Soit  = {0 , . . . , m-1 } un ensemble fini non vide de m symboles, appelé 
alphabet. En
Caml, on représentera le symbole k (pour 0 6 k 6 m - 1) par l'entier k. Cet 
alphabet
sera supposé fixé dans tout l'énoncé.
Un arbre binaire étiqueté par  (simplement appelé, dans ce problème, arbre) est 
soit
l'arbre vide (noté ), soit un quintuplet (S, r, , g, d), où :
(i) S est un ensemble fini non vide dont les éléments sont appelés noeuds ;
(ii) r  S est la racine de S ;
(iii)  : S   est une application associant à chaque noeud de S une étiquette de 
 ;
(iv) g : Sg  S\{r}, où Sg  S, est une application injective associant à un 
noeud u
de Sg un noeud appelé fils gauche de u ;
(v) d : Sd  S\{r}, où Sd  S, est une application injective associant à un noeud 
u
de Sd un noeud appelé fils droit de u.
On dit qu'un noeud v est descendant d'un noeud u s'il existe une séquence de 
noeuds
u0 , u1 , . . . , up  S avec p > 0 telle que u0 = u, up = v et, pour tout 0 6 k 
6 p - 1, soit
uk+1 = g(uk ), soit uk+1 = d(uk ).
On requiert que tout noeud sauf la racine soit le fils gauche ou droit d'un 
unique noeud,
et qu'aucun noeud ne soit à la fois fils gauche et fils droit :
u  S\{r}, |g -1 ({u})| + |d-1 ({u})| = 1.
Par ailleurs, tout noeud de S\{r} doit être descendant de r.
1
1

0

Un arbre admet une représentation graphique naturelle. Par exemple,
l'arbre t0 = ({u0 , u1 , u2 , u3 }, u0 , , g, d) est représenté ci-contre, avec 
:
-- g(u0 ) = u1 , g(u2 ) = u3 et d(u0 ) = u2 ;
-- (u0 ) = (u1 ) = (u3 ) = 1 et (u2 ) = 0 .

1
On utilisera en Caml le type de données suivant pour coder un arbre :
type Arbre = Noeud of Noeud | Vide
and Noeud = { etiquette: int; gauche: Arbre; droit: Arbre; };;

Dans ce codage, un arbre non vide est représenté par une instance du type Noeud 
décrivant
sa racine ; un noeud est décrit par son étiquette (codée comme un entier), son 
fils gauche,
son fils droit ; le fils gauche et le fils droit peuvent, à nouveau, être 
décrits par une
instance du type Noeud, ou par le constructeur Vide, qui décrit leur absence.

Page 3 sur 10

Épreuve d'informatique 2015
Par exemple, l'arbre t0 pourra être décrit par la variable t0 comme suit :
let t0 = Noeud {
etiquette=1;
gauche=Noeud
{etiquette=1; gauche=Vide; droit=Vide};
droit=Noeud
{etiquette=0;
gauche=Noeud {etiquette=1; gauche=Vide; droit=Vide};
droit=Vide}
};;

5 ­ Pour simplifier l'écriture d'arbres, coder en Caml une fonction arbre
telle que si x représente une étiquette x et ag et ad représentent deux arbres
ag et ad , alors arbre x ag ad représente un arbre dont la racine est étiquetée
par x, avec pour fils gauche la racine de ag (avec ses propres fils) et pour
fils droit la racine de ad (avec ses propres fils). Ainsi, cette fonction doit
permettre de construire t0 avec :
let t0 = arbre 1 (arbre 1 Vide Vide)
(arbre 0 (arbre 1 Vide Vide) Vide);;

6 ­ Coder en Caml une fonction taille_arbre prenant en argument une
variable t représentant un arbre t et renvoyant le nombre de noeuds de
l'arbre t.

Langages d'arbres
Soit T  l'ensemble de tous les arbres étiquetés par . Un langage d'arbres sur un
alphabet  est un ensemble (fini ou infini) d'arbres étiquetés par , 
c'est-à-dire un
sous-ensemble de T  .
On considère dans ce problème certains langages particuliers, tous définis sur 
l'alphabet
{0 , 1 } :
-- L0 est l'ensemble des arbres dont au moins un noeud est étiqueté par 0 .
-- Un arbre est complet s'il ne contient aucun noeud ayant un seul fils 
(c'est-à-dire,
tout noeud a un fils gauche si et seulement s'il a un fils droit) ; 
conventionnellement,
 est considéré comme complet. Le langage Lcomplet est l'ensemble de tous les 
arbres
complets.
-- Un arbre (S, r, , g, d) est un arbre-chaîne s'il a uniquement des fils 
gauches :
d-1 (S\{r}) =  ; conventionnellement,  est également un arbre-chaîne. Le 
langage Lchaîne est l'ensemble de tous les arbres-chaînes.
-- Un arbre (S, r, , g, d) est impartial s'il a autant de fils gauches que de 
fils droits,
c'est-à-dire si on a |g(S)| = |d(S)| ; conventionnellement,  est également 
impartial.
On note Limpartial l'ensemble de tous les arbres impartiaux.

Page 4 sur 10

Épreuve d'informatique 2015
7 ­ Pour chacun des quatre langages L0 , Lcomplet , Lchaîne , Limpartial , 
donner (sans justification) un exemple d'arbre avec au moins deux noeuds qui
appartient au langage, et un exemple d'arbre avec au moins deux noeuds qui
n'y appartient pas.
8 ­ Démontrer que tout arbre complet est impartial, mais que la réciproque
est fausse.
9 ­ Démontrer que tout arbre impartial non vide a un nombre impair de
noeuds.

Automates d'arbres descendants déterministes
Un automate d'arbres descendant déterministe (ou simplement automate descendant
déterministe) sur l'alphabet  est un quadruplet A = (Q, q0 , F, ) où :
(i) Q est un ensemble fini non vide dont les éléments sont appelés états ;
(ii) q0  Q est appelé état initial ;
(iii) F  Q est un ensemble dont les éléments sont appelés états finals ;
(iv)  : Q ×   Q × Q est une application appelée fonction de transition ; pour 
tout
q  Q, pour tout   , (q, ) est un couple d'états (qg , qd ).
Un automate descendant déterministe A = (Q, q0 , F, ) reconnaît un arbre t si :
-- soit t =  et q0  F ;
-- soit t = (S, r, , g, d) et il existe une application  : S  Q avec :
(i) (r) = q0 ;
(ii) pour tout u  S, si (qg , qd ) = ((u), (u)) :
-- si g(u) est défini (u  Sg ), alors on a (g(u)) = qg , sinon on a qg  F ;
-- si d(u) est défini (u  Sd ), alors on a (d(u)) = qd , sinon on a qd  F .
Noter que quand une telle application  existe, elle est nécessairement unique.
Le langage reconnu par un automate descendant déterministe A , noté L(A ), est
l'ensemble de tous les arbres reconnus par A .
10 ­ Donner un automate descendant déterministe reconnaissant le langage 
Lchaîne ; aucune justification n'est demandée.
11 ­ Montrer qu'il n'existe pas d'automate descendant déterministe qui
reconnaît L0 .
En Caml, un état qi de Q = {q0 , . . . , qn-1 } est codé par l'entier i. 
L'ensemble des
états finals F est codé par un vecteur de booléens finals_desc de taille n, tel 
que
finals_desc.(i) contient Vrai si et seulement si qi  F . Enfin, les transitions 
sont codées
par une matrice de couples d'entiers, telle que transitions_desc.(i).(k) est le 
couple
(g,d) vérifiant (qg , qd ) = (qi , k ).
On représente ainsi en Caml un automate descendant déterministe (Q, q0 , F, ) 
avec le
type suivant :

Page 5 sur 10

Épreuve d'informatique 2015

type Automate_Descendant_Deterministe = {
finals_desc: bool vect;
transitions_desc: (int*int) vect vect
};;

12 ­ Pour un automate descendant déterministe A = (Q, q0 , F, ) et
q  Q, on note Aq l'automate descendant déterministe (Q, q, F, ) identique
à A sauf pour l'état initial. Coder une fonction applique_desc telle que
applique_desc add q t, où add représente un automate descendant déterministe A 
= (Q, q0 , F, ), q un état q  Q et t un arbre t = (S, r, , g, d),
renvoie un booléen qui vaut Vrai si et seulement Aq reconnaît t.
13 ­ En utilisant applique_desc, coder une fonction evalue_desc telle
que evalue_desc add t, où add représente un automate descendant déterministe A 
et t un arbre t, renvoie un booléen qui vaut Vrai si et seulement si
A reconnaît t.

Automates descendants et langages rationnels de mots
À tout mot non vide x = x1 . . . xl avec x1 , . . . , xl  , on associe un 
arbre-chaîne
chaîne(x) = ({u1 . . . ul }, u1 , , g, d) vérifiant : pour 1 6 i 6 l, (ui ) = 
xi et pour 1 6
i 6 l - 1, g(ui ) = ui+1 , d n'étant défini pour aucun ui , et g(ul ) étant non 
défini. Par
convention, chaîne() =  (où le premier  est le mot vide, le second l'arbre 
vide).
Pour un langage de mots L, on définit le langage d'arbres chaîne(L) := 
{chaîne(x) |
x  L}.
14 ­ Soit L un langage de mots, supposé rationnel. Il existe donc un
automate de mots déterministe A = (Q, , q0 , F, ) reconnaissant L. Soient
q1 , q2 6 Q. On construit l'automate d'arbres descendant déterministe A =
(Q  {q1 , q2 }, q0 , F  {q1 },   ) avec pour (q, )  Q × ,   (q, ) := ((q, ), q1 
)
et, pour q  {q1 , q2 } et pour   ,   (q, ) := (q2 , q2 ). Démontrer que A
reconnaît chaîne(L).
15 ­ Montrer que pour tout langage de mots L, si chaîne(L) est reconnu
par un automate d'arbres descendant déterministe, alors L est rationnel.
16 ­ Soit Légal le langage de mots sur l'alphabet {0 , 1 } formé des mots
contenant autant de 0 que de 1 . Supposons par l'absurde qu'il existe un
automate (de mots) déterministe Aégal reconnaissant Légal et soit k le nombre
d'états de Aégal . En considérant le mot x = 0k 1k , montrer que l'on aboutit à
une contradiction, et que donc Légal n'est pas un langage rationnel.
En déduire qu'il n'existe aucun automate descendant déterministe reconnaissant 
chaîne(Légal ).

Page 6 sur 10

Épreuve d'informatique 2015

Automates d'arbres ascendants
Un automate d'arbres ascendant (ou simplement automate ascendant) sur 
l'alphabet 
est un quadruplet A = (Q, I, F, ) où :
(i) Q est un ensemble fini non vide dont les éléments sont appelés états ;
(ii) I  Q est un ensemble dont les éléments sont appelés états initiaux ;
(iii) F  Q est un ensemble dont les éléments sont appelés états finals ;
(iv)  : Q × Q ×   P(Q), où P(X) désigne l'ensemble des parties de X, est une
application appelée fonction de transition ; pour tout (qg , qd )  Q × Q, et 
tout
  , (qg , qd , ) est un ensemble d'états.
Par exemple, on définit un automate ascendant A0 = (Q, I, F, ) sur l'alphabet
{0 , 1 } avec :
(i) Q = {q0 , q1 } ;
(ii) I = {q0 } ;
(iii) F = {q1 } ;
(iv)  est donnée par la table de transition suivante :

Q×Q

0

1

(q0 , q0 )
(q0 , q1 )
(q1 , q0 )
(q1 , q1 )

{q1 }
{q1 }
{q1 }
{q1 }

{q0 }
{q1 }
{q1 }
{q1 }

Un automate ascendant A = (Q, I, F, ) reconnaît un arbre t si :
-- soit t =  et I  F 6=  ;
-- soit t = (S, r, , g, d) et il existe une application  : S  Q avec :
(i) (r)  F ;
(ii) pour tout u  S, il existe (qg , qd )  Q × Q tels que (u)  (qg , qd , (u)) 
et :
-- si g(u) est défini (u  Sg ), alors on a (g(u)) = qg , sinon qg  I ;
-- si d(u) est défini (u  Sd ), alors on a (d(u)) = qd , sinon qd  I.
Noter que, contrairement au cas des automates descendants déterministes, quand 
une
telle application  existe, elle n'est pas nécessairement unique.

Page 7 sur 10

Épreuve d'informatique 2015
On observe que A0 ne reconnaît pas  (car {q0 }  {q1 } = ) et que A0 reconnaît
l'arbre t0 défini page 3 via l'application représentée ci-dessous :
q1
q0

q1
q0

Le langage reconnu par un automate ascendant A , noté L(A ), est l'ensemble de 
tous
les arbres reconnus par A . On dit qu'un langage d'arbres L est rationnel s'il 
existe un
automate ascendant A qui reconnaît L. 1
On dit qu'un automate ascendant (Q, I, F, ) est déterministe si |I| = 1 et, 
pour tout
(qg , qd , )  Q × Q × , |(qg , qd , )| = 1.
17 ­ Montrer que l'on a L(A0 ) = L0 .
18 ­ Soit L un langage d'arbres. Montrer que s'il existe un automate
descendant déterministe A reconnaissant L, alors L est un langage d'arbres
rationnel.
En Caml, un état qi de Q = {q0 , . . . , qn-1 } est codé par l'entier i. 
L'ensemble des
états initiaux I est codé par leur liste initiaux_asc, dans un ordre arbitraire 
; l'ensemble
des états finals F est codé par un vecteur de booléens finals_asc de taille n, 
dont
la composante de position i contient Vrai si et seulement si qi  F . 
Finalement, les
transitions sont codées par un tableau tridimensionnel de listes d'entiers, 
telle que
transitions_asc.(i).(j).(k) est une liste dans un ordre arbitraire des états q 
avec
q  (qi , qj , k ).
On représente ainsi en Caml un automate ascendant (Q, I, F, ) avec le type 
cidessous :
type Automate_Ascendant = {
initiaux_asc: int list;
finals_asc: bool vect;
transitions_asc: int list vect vect vect
};;

1. La notion de langages d'arbres rationnels est distincte de la notion de 
langages de mots rationnels.

Page 8 sur 10

Épreuve d'informatique 2015
L'automate A0 peut alors être codé par :
let aa0 = {
initiaux_asc=[0];
finals_asc = [| false; true |];
transitions_asc=[|
[| [| [1]; [0] |]; [| [1]; [1] |] |];
[| [| [1]; [1] |]; [| [1]; [1] |] |]
|]
};;

19 ­ Coder une fonction nombre_etats_asc prenant en argument la représentation 
aa d'un automate ascendant et renvoyant le nombre d'états de cet
automate.
20 ­ Coder une fonction nombre_symboles_asc prenant en argument la 
représentation aa d'un automate ascendant et renvoyant le nombre de symboles
de l'alphabet sur lequel cet automate est défini.
21 ­ Coder une fonction Caml applique_asc telle que applique_asc aa t,
où aa représente un automate ascendant A = (Q, I, F, ) et t un arbre t,
renvoie une liste sans doublon des états q pour lesquels il existe une 
application
 : S  Q avec (r) = q qui vérifie la condition (ii) de la définition de
reconnaissance d'un arbre par un automate ascendant page 7. Si t = , la
fonction applique_asc doit renvoyer la liste des états initiaux de A . On
pourra utiliser les fonctions utilitaires des questions 1 à 4.
22 ­ En utilisant applique_asc, coder une fonction evalue_asc telle que
evalue_asc aa t, où aa représente un automate ascendant A et t un arbre t,
renvoie un booléen qui vaut Vrai si et seulement si A reconnaît t. On pourra
utiliser la fonction contient.
23 ­ Montrer qu'un langage d'arbres L est un langage d'arbres rationnel si
et seulement s'il existe un automate ascendant déterministe reconnaissant L.
24 ­ Coder deux fonctions Caml identifiant_partie: int list -> int
et partie_identifiant: int -> int list réciproques l'une de l'autre, codant
une bijection entre les parties de J0 ; n - 1K (une partie étant représentée par
une liste d'entiers sans doublon, dans un ordre arbitraire) et les entiers de 0
à 2n - 1. On rappelle qu'en Caml l'expression 1 lsl i calcule l'entier 2i .
25 ­ En s'appuyant sur identifiant_partie et partie_identifiant et sur
la réponse à la question 23, coder une fonction determinise_asc prenant en
argument la représentation aa d'un automate ascendant A et renvoyant la
représentation d'un automate ascendant déterministe reconnaissant le même
langage que A .

Page 9 sur 10

Épreuve d'informatique 2015
26 ­ Montrer que si L est un langage d'arbres rationnel, alors T  \L est
un langage d'arbres rationnel.
27 ­ Coder une fonction complementaire_asc prenant en entrée la représentation 
aa d'un automate ascendant reconnaissant un langage L et renvoyant
la représentation d'un automate ascendant reconnaissant T  \L.
28 ­ Montrer que si L1 et L2 sont deux langages d'arbres rationnels, alors
L1  L2 est un langage d'arbres rationnel.
29 ­ Coder une fonction union_asc prenant en entrée les représentations
aa1 et aa2 de deux automates ascendants reconnaissant respectivement les
langages L1 et L2 et renvoyant la représentation d'un automate ascendant
reconnaissant L1  L2 .
30 ­ Montrer que si L1 et L2 sont deux langages d'arbres rationnels, alors
L1  L2 est un langage d'arbres rationnel.
31 ­ Coder une fonction intersection_asc prenant en entrée les représentations 
aa1 et aa2 de deux automates ascendants reconnaissant respectivement
les langages L1 et L2 et renvoyant la représentation d'un automate ascendant
reconnaissant L1  L2 .
32 ­ Sans chercher à utiliser les propriétés de clôture par union, 
complémentation ou intersection, montrer que le langage Limpartial n'est pas un
langage d'arbres rationnel.
Fin de l'épreuve

Page 10 sur 10

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



Mines Informatique optionnelle MP 2015 -- Corrigé
Ce corrigé est proposé par Charles-Pierre Astolfi (ENS Cachan) ; il a été relu 
par
Benjamin Monmege (ENS Cachan) et Guillaume Batog (Professeur en CPGE).

Ce sujet étudie deux généralisations des automates de mots dans le cas des 
arbres.
Ces automates d'arbres sont par exemple utiles pour analyser une page HTML, qui
peut être vue comme une structure arborescente de balises (une page qui contient
plusieurs paragraphes, chacun contenant du texte ou des images. . .) ou pour 
calculer
la valeur de vérité d'une formule de la logique propositionnelle. Le sujet 
comporte
six parties mêlant programmation et théorie des automates.
· La première partie demande de coder des fonctions sur les listes. La 
complexité
est systématiquement demandée.
· La deuxième partie introduit les arbres binaires étiquetés et fait programmer
quelques fonctions pour les manipuler.
· La troisième partie définit les langages d'arbres, qui sont des 
généralisations
aux arbres des langages de mots. Les questions sont relativement simples afin
de permettre de prendre en main cette nouvelle notion.
· La quatrième partie introduit les automates d'arbres descendants 
déterministes,
qui sont une première généralisation des automates de mots. On traite le cas
de quelques automates particuliers, puis on code l'exécution d'un tel automate
sur un arbre.
· La cinquième partie fait le lien entre les automates d'arbres descendants 
déterministes et les langages de mots.
· La sixième partie est de loin la plus longue (16 questions sur 32) et la plus
difficile. Y sont introduits les automates d'arbres ascendants, qui sont une
deuxième généralisation des automates de mots. Les questions reprennent la
structure d'un cours sur les automates : déterminisation, clôture par union,
complémentaire, intersection, etc. Les questions théoriques sont toutes suivies
d'une question d'implémentation.
Ce sujet est d'une difficulté et d'une longueur peu communes pour le concours
Mines-Ponts. Il est toujours possible d'avancer sans répondre à une question, 
mais à
la condition d'avoir compris toutes les définitions des parties précédentes.

Indications
3 Appliquer récursivement la fonction union.
4 Utiliser une fonction auxiliaire qui à une variable x et une liste l renvoie 
une liste
de couples ayant x comme premier élément et un élément de l comme second.
9 Remarquer que |S| = 1 + |g(Sg )| + |d(Sd )| dans ce cas.
10 Définir un automate à trois états dont l'un, non final, marque le fait qu'un 
noeud
possède un ancêtre fils droit.
11 Considérer les arbres suivants et montrer qu'un automate acceptant t1 et t2 
accepte t3 .
1

1
0
t1

0

1
1

t2

1
t3

14 Construire une exécution de A sur chaîne(x) à partir d'une exécution de A 
sur x
et réciproquement. Vérifier ensuite que L(A )  Lchaîne.
15 Construire un automate de mots qui reconnaît L. La fonction de transition est
presque la projection sur la première composante de la fonction de transition de
l'automate d'arbres reconnaissant chaîne(L).
16 Si un automate à k états reconnaît un mot à 2k états, il existe alors au 
moins un
état qui est visité deux fois.
17 Remarquer qu'on reste dans l'état q0 tant qu'aucune lettre 1 n'est 
rencontrée.
18 Poser pour la fonction de transition de l'automate ascendant
(qg , qd , ) = {q | (q, )   -1 (qg , qd )}
C'est l'ensemble des états menant à (qg , qd ) en lisant  dans l'automate 
descendant
où l'état initial est {q0 } et l'ensemble des états finals est F.
23 Considérer un automate dont l'ensemble des états est P(Q), avec pour état 
initial,
l'ensemble des états initiaux de l'automate de départ et comme états finals les
parties de Q qui contiennent au moins un état final.
24 Utiliser le fait que les entiers de 0 à 2n -1 sont en bijection avec leur 
représentation
binaire sur n bits.
26 Prendre un automate déterministe et échanger les états finals et non finals.
28 Prendre l'union (disjointe) des deux automates.
30 Utiliser les questions 26 et 28.
32 Considérer l'ensemble des arbres dont le seul noeud binaire est à la racine 
puis
suivi d'une branche à gauche avec uniquement des fils gauches, et une branche à
droite avec uniquement des fils droits.

Fonctions utilitaires
1 La liste li contient x si et seulement si x est le premier élément de li ou 
si la
liste li privée de son premier élément contient x. Parcourons ainsi 
récursivement la
liste li à la recherche de x.
let rec contient li x =
match li with
| [] -> false
| t::q -> t = x || contient q x;;
La fonction examine chacun des éléments de la liste au plus une fois. En notant
 la liste codée par li et || sa longueur, on en conclut que
La complexité de contient est O(||).
La librairie standard de Caml contient la fonction mem : 'a -> 'a list ->
bool qui réalise la même opération que contient, à l'ordre des arguments
près. Cependant, il serait maladroit de l'appeler ici, l'énoncé demandant 
plutôt de recoder cette fonction.
2 On parcourt récursivement la liste l1 pour en extraire tous les éléments qui 
sont
dans l1 sans être dans l2 et lorsqu'on a parcouru entièrement l1, on adjoint la 
liste
des éléments extraits à l2. Les éléments de cette liste sont donc des éléments 
qui
sont dans l1 ou dans l2 et apparaissent exactement une fois, puisque les listes 
sont
supposées sans doublon.
let rec union l1 l2 =
match l1 with
| [] -> l2
| t::q -> if contient l2 t then union q l2 else t::(union q l2);;
Notons 1 (respectivement 2 ) la liste codée par l1 (respectivement l2). La 
fonction réalise |1 | appels à contient, dont la complexité est ici O(|2 |). 
Ainsi,
La complexité de union est O(|1 ||2 |).
Comme pour la question précédente, la librairie standard de Caml
contient la fonction union : 'a list -> 'a list -> 'a list, qui fait la
même chose. À nouveau, il est clair que le sujet demande de la réimplémenter.
Une façon plus efficace de procéder aurait été de d'abord trier chacune
des deux listes puis de les fusionner. En effet, fusionner deux listes triées 
peut
s'effectuer en O(|1 | + |2 |). Le tri s'effectuant en O(|1 | log|1 | + |2 | 
log|2 |),
la complexité totale est alors O(|1 | log|1 | + |2 | log|2 |). Cependant, 
l'énoncé
demande explicitement d'utiliser la fonction contient et n'oriente donc pas
vers cette autre possibilité.
3 Il suffit d'appliquer récursivement la fonction union à chacune des listes de 
l.
let rec fusion l =
match l with
| [] -> []
| li::q -> union li (fusion q);;

Avec les notations de l'énoncé, le i-ème appel récursif à fusion réalise 
l'union de
k
P
la liste i avec une liste de longueur majorée par
|j | 6 L. D'après la question 2,
j=i+1

cet appel a une complexité en O (|i | L). En sommant sur i entre 1 et k,
La complexité de fusion est en O(L2 ).
4 Définissons tout d'abord une fonction auxiliaire couplage : 'a -> 'b list ->
('a * 'b) list. Étant donnés un élément x et une liste l, couplage x l renvoie
une liste de couples dont le premier élément est x et le second un des éléments 
de l.
En appliquant couplage à chaque élément de l1 et sur la liste l2, on obtient une
liste de listes dont la concaténation donne le produit cartésien.
let rec couplage x l2 =
match l2 with
| [] -> []
| t::q -> (x,t)::(couplage x q);;
let rec concat l1 l2 = match l1 with
| [] -> l2
| t::q -> t::(concat q l2);;
let rec produit l1 l2 =
match l1 with
| [] -> []
| x::q -> concat (couplage x l2) (produit q l2);;
En notant 1 et 2 les listes codées par l1 et l2, la fonction couplage a une
complexité en O(|2 |) et retourne une liste de taille 2 . Chacun des |1 | 
appels récursifs
de produit coûte O(|2 |) (qui est le coût de l'appel à couplage et concat). 
Ainsi,
La complexité de produit est en O(|1 ||2 |).

Arbres binaires étiquetés
5 La fonction arbre : int -> Arbre -> Arbre -> Arbre fait utiliser la syntaxe
de la déclaration d'enregistrements en Caml.
let arbre x ag ad = Noeud { etiquette=x; gauche=ag; droite=ad };;
6 On procède par récurrence sur l'arbre : si celui-ci est vide, sa taille est 
0. Sinon,
sa taille est égale à la somme des tailles de chacun de ses sous-arbres gauche 
et droit
plus un pour sa racine.
let rec taille_arbre t =
match t with
| Vide -> 0
| Noeud n -> 1 + taille_arbre n.gauche + taille_arbre n.droite;;