TD 15 : Automates d’arbres ascendants et descendants

EX 1. Automates d’arbres

1.

Automate d’arbres qui accepte les arbres binaires avec un nombre pair de $a$ :

$𝛴 = \lbrace a, b \rbrace$

Construire un automate d’arbres qui accepte les arbres binaires sur $𝛴$ avec un nombre pair de $a$.

\[𝒜 ≝ ⟨Q, 𝛴, 𝛿, F⟩\] \[Q = \lbrace \underbrace{q_0}_{\text{ nombre pair }}, \underbrace{q_1}_{\text{ nombre impair }} \rbrace \\ F = \lbrace q_f \rbrace\] \[𝛿 ≝ \lbrace (a, q_1), (b, q_0), (q_i, q_j, x, q_{i+j+1_{x=a} \mod 2}) \mid 0 ≤ i, j ≤ 1 \rbrace\]

2.

  digraph {
    rankdir=TB;
    subgraph cluster_0 {
      label = "t_1";
      c; a; b;
    }
    c -> a[label="d_1"];
    c -> b[label="d_2"]
  }

  digraph {
    rankdir=TB;
    c1[label="c"];
    a1[label="a"];
    b1[label="b"];
    subgraph cluster_0 {
      subgraph cluster_1 {
        label = "t_1";
        c; a; b;
      }
      label = "t_2";
      c1; a1; b1;
    }
    c -> a[label="d_1"];
    c -> b[label="d_2"];
    c1 -> a1[label="d_1"];
    c1 -> c[label="d_2"];
    c1 -> b1[label="d_3"];
  }

Reconnaissance de l’arbre $t_1$ :

\[𝛿 ≝ \lbrace (a, q_a), (b, q_b), (q_a, q_b, c, q_f) \rbrace\]

Pour reconnaître aussi les autres arbres $t_i$ :

\[𝛿 ≝ \lbrace (a, q_a), (b, q_b), (q_a, q_b, c, q_f), (q_a, q_f, q_b, c, q_f) \rbrace\] 
  digraph {
    rankdir=BT;
    qa_qb_c_qf[style=invis, height=0, label=""];
    qa_qf_qb_c_qf[style=invis, height=0, label=""];
    q_a -> qa_qb_c_qf[label="1"];
    q_b -> qa_qb_c_qf[label="2"];
    qa_qb_c_qf -> q_f[label="c"];
    q_a -> qa_qf_qb_c_qf[label="1"];
    q_f -> qa_qf_qb_c_qf[label="2"];
    q_b -> qa_qf_qb_c_qf[label="3"];
    qa_qf_qb_c_qf -> q_f[label=" c"];
  }

3.

Soit $L⊆𝛴^\ast$ régulier, reconnu par un automate déterministe $A_L ≝ ⟨𝛴_L, Q_L, I_L, F_L, 𝛿_L⟩$.

Construire un AA $𝒜$ tq $𝒜$ reconnaît tous les arbres $t$ tq $Fr(t)∈L$.

Ascendant

On va reconnaître des arbres en peigne :

  digraph {
    rankdir=TB;
    c1, c2, c3, c4[label="c"];
    a1, a2[label="a"];
    b1, b2[label="b"];
    c1 -> a1, c2;
    c2 -> b1, c3;
    c3 -> a2, c4;
    c4 -> b2;
  }
\[A_L ≝ ⟨𝛴_L, Q_L, I_L, F_L, 𝛿_L⟩ \\ 𝒜 ≝ ⟨𝛴, \lbrace q_a, q_b \rbrace ∪ Q, 𝛿', F⟩\] \[𝛿' ≝ \lbrace (a, q_a), (b, q_b), \\ (q_a, c, i \cdot a), (q_b, c, i \cdot b), \\ (q, q_a, c, q \cdot a), (q, q_b, c, q \cdot b) \mid q∈Q \rbrace\]

Descendant

\[A_L ≝ ⟨Q_L, \lbrace a, b \rbrace, q_0, F, 𝛿⟩ \\ 𝒜 ≝ ⟨Q', \lbrace a, b, c \rbrace, 𝛿', F'⟩\]

avec

  • $Q’ = Q × Q$
  • $F’ = \lbrace q_0 \rbrace × F$
\[𝛿 = \lbrace (a, (q,q')) \mid (q, a, q') ∈ 𝛿 \rbrace \\ ∪ \lbrace (b, (q,q')) \mid (q, b, q') ∈ 𝛿 \rbrace \\ ∪ \lbrace \big((q, q''), (q'', q'), c, (q, q')\big) \mid q'', q, q' ∈Q \rbrace\]

Ex :

Pour l’automate

  digraph {
    rankdir=LR;
    b[style=invis, height=0, label=""];
    q_1[shape=doublecircle]
    b -> q_0;
    q_0 -> q_1[label="a"];
    q_1 -> q_0[label="b"];
  }

et le mot $w ≝ aba$

Run de $w$ dans l’automate d’arbres ascendant :

  digraph {
    rankdir=TB;
    c1[label="c\n q_0 . a = q_1"];
    c2[label="c\n q_1 . b = q_0"];
    c3[label="c\n q_0 . a = q_1"];
    a1, a2[label="a\n q_a"];
    b1[label="b\n q_b"];
    c1 -> a1, c2;
    c2 -> b1, c3;
    c3 -> a2;
  }

Run de $w$ dans l’automate d’arbres descendant :

  digraph {
    rankdir=TB;
    c1[label="c \n (q_0, q_1)"];
    c2[label="c \n (q_0, q_0)"];
    a1[label="a\n (q_0, q_1)"];
    a2[label="a\n (q_0, q_1)"];
    b1[label="b\n (q_1, q_0)"];
    c1 -> a1, c2;
    c2 -> a2, b1;

  }

4.

$L$ langages d’arbres reconnaissable.

Mq $Fr(L)$ est algébrique en construisant une grammaire

\[G = ⟨Q ∪ \lbrace S \rbrace, 𝛴, P, S⟩\] \[\begin{align*} P = \; & S ⟶ q_1 ⋯ q_n && ∀ (q_1, \ldots, q_n, a, q) ∈ 𝛿, a∈𝛴, q ∈ F\\ & q ⟶ q_1 ⋯ q_n && ∀ (q_1, \ldots, q_n, a, q) ∈ 𝛿 \\ & q ⟶ a && ∀ (a, q) ∈ 𝛿 \end{align*}\]

EX 2

AA déterministe ascendant :

ssi pour toute famille $q_1, ⋯, q_n, a$, il y a au plus un $q$ tq $(q_1, \ldots, q_n, a, q) ∈ 𝛿$

AA déterministe descendant :

ssi il existe un seul état final, et pour toute paire $(a, q) ∈ 𝛴 × Q$, il y a au plus un $n$ et un $n$-uplet tq $(q_1, \ldots, q_n, a, q) ∈ 𝛿$

Les déterministes ascendants sont aussi expressifs que les automates d’arbres en général, mais ce n’est pas le cas des déterministes descendants.

Exs : Langages pas reconnu par automate d’arbre descendant :

Langage des arbres ayant un nombre pair de noeuds internes ⟶ alors on n’a qu’une seule transition de la forme $(q_0, q_1, c, q_i)$, ce qui ne couvre pas tous les cas de figure.

On peut déterminiser les automates d’arbres ascendants avec l’automate des parties.

Puis, en déterminisant, on montre que les AA ascendants sont clos par complémentarité.

Les langages d’arbres sont fermés par intersection ⟶ langages d’arbre contiennent strictement les langages algébriques.

Ex :

\[\lbrace a^n b^n c^n \mid n ≥ 1 \rbrace\]

reconnu

  digraph {
    rankdir=TB;
    c1, c2, c3, c4[label=""];
    d1, d2, d3[label=""];
    a1, a2, a3[label="a"];
    b1, b2, b3, b4[label="b"];
    c11, c22, c33, c44[label="c"];
    c1 -> a1, c2;
    c2 -> a2, c3;
    c3 -> a3, c4;
    c1 -> b1, d1, c11;
    d1 -> b2, d2, c22;
    d2 -> b3, d3, c33;
    d3 -> b4, c44;
  }

Leave a comment