Exercices automates d'arbre Théorie des langages-téléch...

Théorie des langages : Exercices automates d'arbre

Télécharger PDF

Option Informatique : Corrigé Automates d’Arbres (Mines 2015)

Partie I. Fonctions utilitaires

Question 1. Il s’agit de redéfinir la fonction (fun li x → mem x li) :

let rec contient li x =
  match li with
  | [] → false
  | t::q → x = t || contient q x ;;

La fonction contient est de complexité O(|li|).

Question 2. Il s’agit maintenant de redéfinir la fonction union :

let rec union l1 l2 =
  match l1 with
  | [] → l2
  | t::q when contient l2 t → union q l2
  | t::q → t::(union q l2) ;;

La fonction contient est appelée |l1| fois lors du calcul de l’union de deux listes l1 et l2, donc la complexité de la fonction union est en O(|l1| × |l2|).

Question 3. On définit :

let rec fusion l =
  it_list union [] l ;;

La complexité C(k) de la fonction fusion appliquée à l = (l1, ..., lk) vérifie la relation de récurrence :

C(k) = C(k−1) + O((|l1| + |l2| + ... + |lk−1|) × |lk|).

On en déduit que C(k) = O(k ∑ i=1 |li| × (i−1 ∑ j=1 |lj|)), quantité que l’on peut majorer par un O(L²) avec L = |l1| + ... + |lk|.

Question 4. On définit enfin le produit cartésien de deux listes :

let rec produit l1 l2 =
  match l1 with
  | [] → []
  | t::q → (map (fun x → (t, x)) l2) @ (produit q l2) ;;

Le coût de la concaténation est linéaire par rapport à son premier argument, donc la complexité de la fonction produit vérifie la relation :

C(|l1|, |l2|) = C(|l1|−1, |l2|) + O(|l2|).

Sachant que C(0, |l2|) = O(1), on en déduit que C(|l1|, |l2|) = O(|l1| × |l2|).

Partie II. Arbres binaires étiquetés

Question 5.

let arbre x ag ad = Noeud {etiquette = x; gauche = ag; droit = ad} ;;

Question 6.

let rec taille_arbre =
  function
  | Vide → 0
  | Noeud n → 1 + taille_arbre n.gauche + taille_arbre n.droit ;;

Partie III. Langages d’arbres

Question 7.

Un arbre appartient au langage L si 0α 0α 0α 1α 1 est reconnu. Un arbre complet appartient à L si 0α 0α 0α 0α 0 est reconnu. Une chaîne appartient à L si 0α 0α 0α 0α 0 est reconnu. Un arbre impartial appartient à L si 0α 0α 0α 0α 0 est reconnu.

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 suivant, impartial mais non complet :

α 0α 0α 0α 0α 0

Question 9. Par hypothèse, pour tout u ∈ S\{r}, |g⁻¹({u})| + |d⁻¹({u})| = 1, donc S = {r} ∪ g(Sg) ∪ d(Sd), cette union étant disjointe.

Puisque g et d sont 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. Posons Q = {q0, q1, q2}, F = {q0, q1} et définissons δ par :

Pour tout c ∈ Σ, δ(q0, c) = (q0, q1), δ(q1, c) = (q2, q2), δ(q2, c) = (q2, q2).

Montrons que cet automate A↓ reconnaît L chaîne.

Considérons un arbre-chaîne t : on a Sd = ∅. Si t = ε, alors t est reconnu puisque q0 ∈ F. Sinon, considérons l’application φ : S → Q définie par : pour tout u ∈ S, φ(u) = q0.

- Pour tout u ∈ S, on a δ(φ(u), λ(u)) = δ(q0, λ(u)) = (q0, q1).

- Si u ∈ Sg, alors φ(g(u)) = q0 et si u < Sg, alors q0 ∈ F.

- Et dans tous les cas, u < Sd et q1 ∈ F.

Réciproquement, si t n’est pas un arbre-chaîne, il existe un sommet u tel que u ∈ Sd. Dans ce cas, s’il existait une fonction φ vérifiant les conditions requises pour que A↓ reconnaisse t, on aurait φ(d(u)) = q1. Or δ(q1, λ(d(u))) = (q2, q2) et q2 ∉ F :

d(u) doit nécessairement avoir un fils (gauche ou droite). Considérons alors un descendant v de d(u) n’ayant pas de fils (il en existe forcément). Puisque q2 est un puits, on a φ(v) = q2, et puisque q2 ∉ F, ceci contredit les propriétés de φ.

Question 11.

Considérons un automate descendant déterministe A↓ = (Q, q0, F, δ) reconnaissant L0. Il doit en particulier reconnaître les arbres suivants :

α 1α 0α 1
α 1α 1α 0

Soit (q1, q2) = δ(q0, α1).

Posons (q3, q4) = δ(q2, α1). Puisque l’arbre de gauche est reconnu, on doit avoir q3 ∈ F et q4 ∈ F.

Posons (q5, q6) = δ(q1, α1). Puisque l’arbre de droite est reconnu, on doit avoir q5 ∈ F et q6 ∈ F.

Mais alors A↓ reconnaît l’arbre suivant, ce qui est absurde :

α 1α 1α 1

Question 12.

let rec applique_desc add q =
  function
  | Vide → add.finals_desc.(q)
  | Noeud t →
      let qg, qd = add.transitions_desc.(q).(t.etiquette) in
      applique_desc add qg t.gauche && applique_desc add qd t.droit ;;

Question 13.

let eval_desc add t = applique_desc add 0 t ;;

Partie V. Automates descendants et langages rationnels de mots

Question 14. Soit x un mot de L, et t = chaîne(x). Si x = ε, alors q0 ∈ F car A reconnaît x, et t = ε est bien reconnu par A↓.

Si x = x1 ... xl, il existe un chemin q0 x1 → q1 x2 → ... xl → ql dans A tel que ql ∈ F.

Posons t = ({u1, ..., ul}, u1, λ, g, d) et définissons la fonction φ : ui → qi−1.

- On a bien φ(u1) = q0.

- Pour tout i ∈ {1, ..., l−1}, δ′(φ(ui), xi) = (qi, q′1) où g(ui) est défini et φ(g(ui)) = φ(ui+1) = qi, d(ui) n’est pas défini mais q′1 ∈ F ∪ {q′1}.

- Pour i = l, δ′(φ(ul), xl) = (ql, q′l). Ni g(ul) ni d(ul) ne sont définis, mais ql ∈ F et q′l ∈ F ∪ {q′l}.

De ceci, il résulte que A↓ reconnaît t.

Réciproquement, considérons un arbre t reconnu par A↓ et montrons qu’il existe un mot x ∈ L tel que chaîne(x) = t.

Si t = ε, alors q0 ∈ F, donc ε ∈ L et t = chaîne(ε).

Si t ≠ ε, posons t = (S, r, λ, g, d). Si r ∈ Sd, alors φ(d(r)) = q′1 et δ(φ(d(r)), λ(d(r))) = (q′2, q′2). Puisque q′2 est un état puits, en considérant un descendant v de d(r) n’ayant pas de fils, on obtient une absurdité puisque q′2 ∉ F ∪ {q′1}. Ainsi, r n’a pas de fils droit, et en procédant récursivement, on montre de la même manière que t est un arbre-chaîne.

On peut donc poser S = {u1, ..., ul} et r = u1, avec g(ui−1) = ui et ui−1 < Sd, et définir le mot x = x1 ... xl avec xi = λ(ui). Ainsi, t = chaîne(x), et en posant qi égale à la composante gauche de δ′(ui+1, xi), on obtient un chemin q0 x1 → q1 x2 → ... xl → ql menant à un état acceptant dans A, ce qui prouve que x ∈ L.

Question 15. Soit A↓ = (Q, q0, F, δ) un automate d’arbres descendant déterministe qui reconnaît chaîne(L). On définit l’automate de mots déterministe complet A = (Q, Σ, q0, F, δ′) en convenant que pour tout q ∈ Q et α ∈ Σ, si δ(q, α) = (qg, qd), alors δ′(q, α) = qg.

Si x = x1 ... xl ∈ Σ*, on définit la suite d’états q1, ..., ql en posant : pour tout i ∈ {1, ..., l}, qi est la composante gauche de δ(qi−1, xi). Par construction, à cette suite d’états est associé un chemin q0 x1 → q1 x2 → ... xl → ql dans A. Or chaîne(x) est reconnu par A↓ si et seulement si ql ∈ F, et x est reconnu par A si et seulement si ql ∈ F. On en déduit que si chaîne(L) est reconnu par A↓, alors L est reconnu par A, et en particulier L est rationnel.

Combiné à la question précédente, nous avons prouvé qu’un langage L est rationnel si et seulement s’il existe un automate d’arbre descendant déterministe qui reconnaît chaîne(L).

Question 16. Il s’agit d’appliquer le lemme de l’étoile.

Considérons le chemin q0 α0 → q1 α0 → ... α0 → qk α1 → qk+1 α1 → ... α1 → q2k. Puisque x est reconnu par A, ce chemin mène à un état q2k ∈ F. Mais A n’a que k états, donc il existe 0 ≤ i < j ≤ 2k tel que qi = qj (principe des tiroirs).

Considérons le mot y = αj 0 αj−i0 ... αk−j 0 αk+1 = αk+j−i 0 αk+1. Il est reconnu par A puisque le chemin q0 αj 0 → qj = qi αj−i0 → qj αk−j 0 → qk αk+1 → q2k