Théorie des langages : Exercices automates d'arbre
Télécharger PDFoption informatique
Corrigé : automates d’arbre (Mines 2015)
Partie I.
Fonctions utilitaires
Question 1.Il s’agit de redéfinir la fonction(fun li x−> mem x li):
let reccontient li x =matchliwith
| []−> false
| t::q−> x = t || contient q x ;;
La fonctioncontientest de complexité O(|li |).
Question 2.Il s’agit maintenant de redéfinir la fonctionunion:
let recunion l1 l2 =matchl1with
| []−> l2
| t::q when contient l2 t−> union q l2
| t::q−> t::(union q l2) ;;
La fonctioncontientest appelée|l1 |fois lors du calcul de l’union de deux listesl1 etl2 , donc la complexité de la fonction
unionest en O(|l1 |×|l2 |).
Question 3.On définit :
let recfusion l = it_list union [] l ;;
La complexité C(k) de la fonctionfusionappliquée àl= (l1 , . . . , lk ) vérifie la relation de récurrence :
C(k) = C(k−1) + O( (|l 1|+|l 2
|+···+|lk−1 |) ×|lk |) .
On en déduit que C(k) = O( k∑ i=1|l i|× (i−1 ∑j=1 |lj |) )
, quantité que l’on peut majorer par un O(L2 ) avec L =|l1 |+···+|lk |.
Question 4.On définit enfin le produit cartésien de deux listes :
let recproduit l1 l2 =matchl1with
| []−> []
| t::q−> (map (functionx−> (t, x)) l2) @ (produit q l2) ;;
Le coût de la concaténation est linéaire vis-vis-vis de son premier argument, donc la complexité de la fonctionproduit
vérifie la relation :C(|l1 |,|l2 |) =C(|l1 |−1,|l2 |) + O(|l2 |). Sachant queC(0,|l2 |) = O(1)on en déduit queC(|l1 |,|l2 |) = O(|l1 |×|l2 |).
Partie II.
Arbres binaires étiquetés
Question 5.
letarbre x ag ad = Noeud {etiquette = x; gauche = ag; droit = ad} ;;
Question 6.
let rectaille_arbre =function
| Vide−> 0
| Noeud n−> 1 + taille_arbre n.gauche + taille_arbre n.droit ;;
page 1
Partie III.
Langages d’arbres
Question 7.
appartient au langagen’appartient pas au langageL 0α 0α 0α 1α 1L completα 0α 0α 0α 0α 0L chaîneα 0α 0α 0α 0α 0L impartialα 0α 0α 0α 0α 0
Question 8.Un arbre complet est caractérisé par l’égalité :Sg =Sd , un arbre impartial par l’égalité :|Sg |=|Sd |. Tout
arbre complet est donc impartial, mais la réciproque est fausse, comme le montre l’arbre ci-dessous, impartial mais non
complet :α 0α 0α 0α 0α 0
Question 9.Par hypothèse, pour toutu∈S\{r},|g−1 ({u})|+|d−1 ({u})|= 1doncS={r}∪g(Sg )∪d(Sd ), cette union étant
disjointe.
Puisquegetdsont injectives,|S|= 1 +|Sg |+|Sd |et puisque l’arbre est impartial,|Sg |=|Sd |, ce qui montre que|S|est impair.
Partie IV.
Automates d’arbres descendants déterministes
Question 10.PosonsQ={q0 , q1 , q2 },F={q0 , q1 }et définissonsδpar :∀c∈Σ,δ(q0 , c) = (q0 , q1 ),δ(q1 , c) = (q2 , q2 ),δ(q2 , c) =(q 2
, q2 ).
Montrons que cet automateA↓ reconnaîtLchaîne , en commençant par considérer un arbre-chaînet: on aSd =∅. Sit=ε,t
est reconnu puisqueq0 ∈F. Sinon, considérons l’applicationφ: S→Q définie par∀u∈S,φ(u) =q0 .
– Pour toutu∈S, on aδ(φ(u),λ(u)) =δ(q0 ,λ(u)) = (q0 , q1 ).
– Siu∈Sg , on a bienφ(g(u)) =q0 , siu<Sg , on a bienq0 ∈F.
– Et dans tous les cas,u<Sd etq1 ∈F.
Réciproquement, sitn’est pas un arbre-chaine, il existe un sommetutel queu∈Sd . Dans ce cas, s’il existait une fonction
φvérifiant les conditions requise pour queA↓ reconnaisset, on auraitφ(d(u)) =q1 . Orδ(q1 ,λ(d(u))) = (q2 , q2 ) etq2 <F:
d(u) doit nécessairement avoir un fils (gauche ou droite). Considérons alors un descendantvded(u) n’ayant pas de fils (il
en existe forcément). Puisqueq2 est un puits, on aφ(v) =q2 , et puisque queq2 <F, ceci contredit les propriétés deφ.
Question 11.
Considérons un automate descendant déterministeA↓ = (Q, q0 ,F,δ) reconnaissantL0 . Il doit en particulier
reconnaître les arbres suivants :α 1α 0α 1et α1 α1 α0 page 2
Soit (q1 , q2 ) =δ(q0 ,α1 ).
Posons (q3 , q4 ) =δ(q2 ,α1 ). Puisque l’arbre de gauche est reconnu on doit avoirq3 ∈F etq4 ∈F.
Posons (q5 , q6 ) =δ(q1 ,α1 ). Puisque l’arbre de droite est reconnu on doit avoirq5 ∈F etq6 ∈F.
Mais alorsA↓ reconnaît l’automate suivant, ce qui est absurde :α 1α 1α 1
Question 12.
let recapplique_desc add q =function
| Vide−> add.finals_desc.(q)
| Noeud t−>letqg, qd = add.transitions_desc.(q).(t.etiquette)in
applique_desc add qg t.gauche && applique_desc add qd t.droit ;;
Question 13.
letevalue_desc add t = applique_desc add 0 t ;;
Partie V.
Automates descendants et langages rationnels de mots
Question 14.Soitxun mot deL, ett=chaîne(x). Six=εalorsq0 ∈FcarAreconnaîtx, ett=εest bien reconnu parA↓ .Six=x 1···x l
, il existe un cheminq0 x1 −→q1 x2 −→···x l−→q l
dansAtel queql ∈F.
Posonst= ({u1 , . . . , ul }, u1 ,λ, g, d) et définissons la fonctionφ:ui 7→qi−1 .
– on a bienφ(u1 ) =q0 ;– pour touti∈~1, l−1,δ′ (φ(ui ), xi ) = (qi , q′ 1).g(u i
) est défini etφ(g(ui )) =φ(ui+1 ) =qi ,d(ui ) n’est pas défini maisq ′1 ∈F∪{q′ 1}. – pouri=l,δ′ (φ(ul ), xl ) = (ql , q′ 1
). Nig(ul ) nid(ul ) ne sont définis, maisql ∈F etq′ 1∈F∪{q ′1 }.
De ceci il résulte queA↓ reconnaîtt.
Réciproquement, considérons un arbretreconnu parA↓ et montrons qu’il existe un motx∈L tel que chaîne(x) =t.
Sit=εalorsq0 ∈F doncε∈L ett= chaîne(ε).
Sit,ε, posonst= (S, r,λ, g, d). Sir∈Sd ,φ(d(r)) =q′ 1
etδ(φ(d(r)),λ(d(r))) = (q′ 2
, q′ 2
). Puisqueq′ 2
est un état puits, en
considérant un descendantsded(r) n’ayant pas de fils on obtient une absurdité puisqueq′ 2
<F∪{q′ 1}. Ainsi,rn’a pas de fils droit, et en procédant récursivement on montre de la même manière quetest un arbre-chaîne. On
peut donc poserS={u1 , . . . , ul }etr=u1 avecg(ui−1 ) =ui etui−1 <Sd , et définir le motx=x1 ···xl avecxi =λ(ui ). Ainsi,
t=chaîne(x), et en posantqi égale à la composante gauche deδ′ (ui+1 , xi ) on obtient un cheminq0 x1 −→q1 x2 −→···x l−→q l
menant à un état acceptant dansA, ce qui prouve quex∈L.
Question 15.SoitA ↓
= (Q, q0 ,F,δ) un automate d’arbres descendant déterministe qui reconnaîtchaîne(L). On définit
l’automate de mots déterministe completA= (Q,Σ, q0 ,F,δ′ ) en convenant que pour toutq∈Qetα∈Σ, siδ(q,α) = (qg , qd )alorsδ ′
(q,α) =qg .Six=x 1···x l∈Σ ∗
, on définit la suite d’étatsq1 , . . . , ql en posant : pour touti∈~1, l,qi est la composante gauche deδ(q i−1
, xi ). Par construction, à cette suite d’états est associé un cheminq0 x1 −→q1 x2 −→···x l−→q ldansA. Orchaîne(x) est reconnu parA↓ si et seulement siql ∈F, etxest reconnu parAsi et seulement siql ∈F. On en déduit que
si chaîne(L) est reconnu parA↓ alors L est reconnu parA, et en particulier L est rationnel.
Combiné à la question précédente, nous avons prouvé qu’un langageLest rationnel si et seulement s’il existe un automate
d’arbre descendant déterministe qui reconnaît chaîne(L).
page 3
Question 16.Il s’agit d’appliquer le lemme de l’étoile (qui n’est plus au programme ; il faut donc le re-démontrer).
Considérons le cheminq0 α0 −→q1 α0 −→···α 0−→q kα 1−→q k+1α 1−→··· α1 −→q2k . Puisquexest reconnu parA, ce chemin mène à unétatq 2k
∈F. MaisAn’a quekétats, donc il existe 0< i < j6ktel queqi =qj (c’est le principe des tiroirs).
Considérons le moty=αj 0α j−i0 αk−j 0α k1 =αk+j−i 0α k1 . Il est reconnu parApuisque le cheminq0 αj 0−→q j=q iα j−i0 −→qj αk−j 0−→q kα k1 −→q2k est acceptant. Mais ceci est absurde puisquey<Légal .
On en déduit queLégal n’est pas rationnel, puis, compte tenu de l’équivalence établie aux deux questions précédentes,
qu’il n’existe pas non plus d’automate descendant déterministe reconnaissant chaîne(Légal ).
Partie VI.
Automates d’arbres ascendants
Question 17.Soitt= (S, r,λ, g, d) un arbre de L0 . Définissons la fonctionφ: S→Q en posant :
φ(s) = q1 sisou un de ses descendants est étiqueté parα0 q0 sinon
Puisquet∈L0 on aφ(r) =q1 , et pour toutu∈S,
– siφ(u) =q0 , alorsλ(u) =α1 etφ(u)∈∆(q0 , q0 ,α1 ), et siu∈Sg alorsφ(g(u)) =q0 , siu∈Sd alorsφ(d(u)) =q0 ;
– siφ(u) =q1 alors :
– siu∈Sg ∩Sd et sig(u) etd(u) possèdent tous deux un descendant étiqueté parα0 alorsφ(u)∈∆(q1 , q1 ,λ(u)) ;
– siu∈Sg etu<Sd et sig(u) possède un descendant étiqueté parα0 alorsφ(u)∈∆(q1 , q0 ,λ(u)) ;
– siu<Sg etu∈Sd et sid(u) possède un descendant étiqueté parα0 alorsφ(u)∈∆(q0 , q1 ,λ(u)) ;
– siune possède pas de descendant étiqueté parα0 autre que lui-même, alorsφ(u)∈∆(q0 , q0 ,α0 ).
test donc reconnu parA↑ 0. Soit maintenanttun arbre n’appartenant pas àL0 . Sit=ε,tn’est pas reconnu parA↑ 0
. Et sit= (S, r,λ, g, d) était reconnu,
l’applicationφ:S→Qassociée à cette reconnaissance vérifieraitφ(r) =q1 , et compte tenu de la table de transition
associée à∆,rposséderait au moins un filsuvérifiantφ(u) =q1 . Par induction il existerait une feuillevvérifiantφ(v) =q1 ,
ce qui est absurde puisqueq1 <∆(q0 , q0 ,α1 ).
De ceci il résulte queL(A↑ 0
) = L0 .
Question 18.PosonsA↓ = (Q, q0 ,F,δ), et définissons l’automate ascendantA↑ = (Q,F,{q0 },∆) en posant :∀(q 1
, q2 )∈Q2 ,∀α∈Σ,∆(q1 , q2 ,α) ={ q∈Q∣ ∣∣ δ(q,α) = (q1 , q2 )} .
Soitt∈L. Sit=εalorsq0 ∈Fdonc{q0 }∩F,∅ettest aussi reconnu parA↑ . Sit= (S, r,λ, g, d), notonsφla fonction
associée à la reconnaissance parA↓ de l’arbret. Il est alors aisé de montrer que cette même fonction vérifie les conditions
nécessaires pour queA↑ reconnaisset. Ainsi,t⊂L(A↑ ).
Réciproquement, considérons un arbret∈L(A↑ ). Sit=εalorsq0 ∈Fettest aussi reconnu parA↓ . Sit= (S, r,λ, g, d), soitφ
une fonction associée à cette reconnaissance parA↑ . Là encore, on vérifie que cette même fonctionφvérifie les conditions
pour queA↓ reconnaisset. Ainsi,t∈L.
De ceci il résulte queL(A↑ ) = L et donc que L est un langage d’arbres rationnel.
Question 19.Le nombre d’états est la taille du vecteurfinal_asc:
letnombre_etats_asc aa = vect_length aa.finals_asc ;;
Question 20.Le nombre de caractères de l’alphabet est la troisième dimension du tableautransitions_asc:
letnombre_symboles_asc aa = vect_length aa.transitions_asc.(0).(0) ;;
page 4
Question 21.On procède par induction : on calcule la liste des états possibles qu’on peut associer aux fils gauche et
droit de la racine ; il faut alors fusionner, pour chacun des couples (qg , qd ) obtenus, la liste des états∆(qg , qd ,λ(r)).
let recapplique_asc aa =function
| Vide−> aa.initiaux_asc
| Noeud t−>letlg = applique_asc aa t.gaucheandld = applique_asc aa t.droitin
letp = produit lg ldin
letl = map (function(g, d)−> aa.transitions_asc.(g).(d).(t.etiquette)) pin
fusion l ;;
Question 22.Il reste alors à vérifier qu’un des étatsqobtenus par la fonction précédente vérifieq∈F :
letevalue_asc aa t = exists (functionq−> aa.finals_asc.(q)) (applique_asc aa t) ;;
Question 23.Dans cette question il s’agit de montrer qu’on peut « déterminiser » un automate ascendantA↑ = (Q,I,F,∆).
Nous allons nous inspirer de l’algorithme de déterminisation classique en posantA↑ d
= (Qd ,Id ,Fd ,∆d ) avec :
– Qd =P(Q) ;
– Id ={I};
– Fd ={ A∈P(Q)∣ ∣∣ A∩F,∅} ;
–∀(A,B)∈P(Q)2 ,∀α∈Σ,∆d (A,B,α) ={ ⋃(q 1,q 2)∈A×B ∆(q1 , q2 ,α)} .
Cet automate ascendant est bien déterministe, et reconnait le même langage d’arbre queA↑ .
Question 24.
Une partie de~0, n−1peut être représentée par le graphe de sa fonction caractéristique, lui-même
représenté par l’écriture binaire d’un entier compris entre 0 et 2n −1. Ceci donne les fonctions :
let recidentifiant_partie =function
| []−> 0
| t::q−> (1 lsl t) + (identifiant_partie q) ;;
letpartie_identifiant n =
let recaux acc =function
| 0−> []
| n when n mod 2 = 0−> aux (acc + 1) (n / 2)
| n−> acc::(aux (acc + 1) (n / 2))
inaux 0 n ;;
Question 25.Il faut maintenant mettre en œuvre la construction décrite à la question 23. Sinest le nombre d’états deA ↑
, les états de l’automate déterminisé sont des parties de~0, n−1, qui seront représentées par des entiers compris entre
0 et 2n −1 grâce aux fonctions écrites à la question précédente.
Pour plus de lisibilité, nous allons écrire trois fonctions pour calculer respectivementId ,Fd et∆d . Pour cette dernière
fonction, il faudra construire un tableau tri-dimensionnel. De base,Camlne dispose que des fonctionsmake_vect(pour
les tableaux uni-dimensionnels) etmake_matrix(pour les tableaux bi-dimensionnels). J’ai donc commencé par définir la
fonction :
letmake_trimatrix p q r x =
letm = make_matrix p q [||]in
fori = 0top−1do
forj = 0toq−1do
m.(i).(j) <−make_vect r xdone done;
m ;;
Voici maintenant les trois fonctions annoncées :
page 5
letconstruire_Id aa = [identifiant_partie aa.initiaux_asc] ;;
letconstruire_Fd aa =
letn = nombre_etats_asc aain
letf = make_vect n falsein
fori = 0ton−1do
ifexists (functionk−> aa.finals_asc.(k)) (partie_identifiant i)thenf.(i) <−truedone; f ;;
letconstruire_Deltad aa =
letn = nombre_etats_asc aaandp = nombre_symboles_asc aain
letd = make_trimatrix n n p []in
fori = 0ton−1do
forj = 0ton−1do
fork = 0top−1do
leta = partie_identifiant iandb = partie_identifiant jin
letp = produit a bin
letl = map (function(q1, q2)−> aa.transitions_asc.(q1).(q2).(k)) pin
d.(i).(j).(k) <−[identifiant_partie (fusion l)]done donedone; d ;;
La fonction demandée s’écrit alors :
letdeterminise_asc aa =
{ initiaux_asc = construire_Id aa ;
finals_asc = construire_Fd aa ;
transitions_asc = construire_Deltad aa } ;;
Question 26.NotonsA↑ = (Q,I,F,∆) un automate ascendantdéterministequi reconnaîtL, et définissonsA↑ c
= (Qc ,Ic ,Fc ,∆c )
en posant :Q c
= Q,Ic = I,Fc = Q\F,∆c =∆.
La déterminisation assure l’unicité de la fonctionφreconnaissant un arbre non videt, et ainsi,A↑ c
est un automate
ascendant qui reconnaît le langage d’arbre complémentaire de L.
Question 27.On en déduit la fonction :
letcomplementaire_asc aa =
letaac = determinise_asc aain
{ initiaux_asc = aac.initiaux_asc ;
finals_asc = map_vect (functionb−>notb) aac.finals_asc ;
transitions_asc = aac.transitions_asc } ;;
Question 28.Notons pouri∈{1,2},A↑ i
= (Qi ,Ii ,Fi ,∆i ) un automate ascendant qui reconnaîtLi . Quitte à renommer les
états on peut supposer Q1 et Q2 disjoints. Définissons alorsA↑ = (Q,I,F,∆) en posant :
Q = Q1 ∪Q2 ,I = I1 ∪I2 ,F = F1 ∪F2 et pour la fonction de transition :∆(q 1
, q2 ,α) = ∆1 (q1 , q2 ,α)
si (q1 , q2 )∈Q2 1∆ 2(q 1
, q2 ,α)
si (q1 , q2 )∈Q2 2∅sinon AlorsA↑ reconnaît L1 ∪L2 .
Question 29.On en déduit les fonctions :
page 6
letconstruire_Iu aa1 aa2 =
letn = nombre_etats_asc aa1in
union aa1.initiaux_asc (map (prefix+ n) aa2.initiaux_asc) ;;
letconstruire_Fu aa1 aa2 =
concat_vect aa1.finals_asc aa2.finals_asc ;;
letconstruire_Deltau aa1 aa2 =
letn1 = nombre_etats_asc aa1andp1 = nombre_symboles_asc aa1in
letn2 = nombre_etats_asc aa2andp2 = nombre_symboles_asc aa2in
letd = make_trimatrix (n1 + n2) (n1 + n2) (max p1 p2) []in
fori = 0ton1−1do
forj = 0ton1−1do
fork = 0top1−1do
d.(i).(j).(k) <−aa1.transitions_asc.(i).(j).(k)done donedone; fori = 0ton2−1do
forj = 0ton2−1do
fork = 0top2−1do
d.(n1+i).(n1+j).(k) <−aa1.transitions_asc.(i).(j).(k)done donedone; d ;;
letunion_asc aa1 aa2 =
{ initiaux_asc = construire_Iu aa1 aa2 ;
finals_asc = construire_Fu aa1 aa2 ;
transitions_asc = construire_Deltau aa1 aa2 } ;;
Question 30.De l’égalitéL1 ∩L2 =L1 ∪L2 et des questions 26 et 28 il résulte que siL1 etL2 sont des langages d’arbres
rationnels il en est de même de L1 ∩L2 .
Question 31.On en déduit :
letintersection_asc aa1 aa2 =
complementaire_asc (union_asc (complementaire_asc aa1) (complementaire_asc aa2)) ;;
Remarque. Il serait plus naturel de définir l’intersection parA↑ i
= (Q1 ×Q2 ,I1 ×I2 ,F1 ×F2 ,∆) avec :∆((q 1
, q2 ),(q′ 1
, q′ 2
),α) =∆1 (q1 , q′ 1,α)×∆ 2(q 2
, q′ 2,α) mais la traductionCamlserait délicate vu la contrainte imposée par l’énoncé quant à la représentation des états par des
entiers.
Question 32.Supposons l’existence d’un automate ascendantA↑ = (Q,I,F,∆) reconnaissantL
impartial
, posonsn=|Q|et
posonst= (~−n, n,0,λ, g, d) avec :
–∀s∈~−n, n,λ(s) =α0 ;
–g:~1−n,0→~−n, nest défini parg(s) =s−1 ;
–d:~0, n−1→~−n, nest défini pard(s) =s+ 1.
test impartial donc reconnu parA↑ . Soitφune fonction répondant aux exigences de la page 4.
Puisquen=|Q|, le principe des tiroirs affirme l’existence de 06i < j6ntel queφ(i) =φ(j).
Considérons alors l’arbret′ = (~−n, i∪~j+ 1, n,0,λ′ , g′ , d′ ) défini par :
–∀s∈~−n, i∪~j+ 1, n,λ(s) =α0 ;
–g:~1−n,0→~−n, nest défini parg(s) =s−1 ;
–d:~0, i∪~j+ 1, n−1→~−n, nest défini pard(i) =j+ 1 etd(s) =s+ 1 sinon.Alorst ′
n’est pas impartial mais toujours reconnu parA↑ , ce qui est absurde.
Le langage d’arbre L
impartial
n’est donc pas rationnel.
page 70 −1−2 ·1−n −n1 2· n−1n L’arbret, étiqueté par ses sommets.0 −1−2 ·1−n −n1 i
j+ 1n L’arbret′ , étiqueté par ses sommets.
page 8