Exercises 1 : Recognizable Tree Languages and Finite Tree Automata

EX 1: First constructions

\[\newcommand{\dom}{\mathop{\rm dom}\nolimits}\]

Let $𝔉 ≝ \lbrace f(2), g(1), a(0)\rbrace$.

\[G(t) ≝ \lbrace f(f(a, u), g(v)) \mid u, v∈T(𝔉) \rbrace\]

Top-down: $q_0 ⟶^\ast t$

Bottom-up: $t ⟶ q_f$

  graph {
    rankdir= TB;
    f1[label="f"];
    f2[label="f"];
    a[label="a"];
    b1[label="."];
    b2[label="."];
    f1 -- f2, g;
    g -- b2;
    f2 -- a, b1;
  }

Top-down

$I ≝ \lbrace q_{f_1} \rbrace$

• $q_{f_1}(f(x, y)) ⟶ f(q_{f_2}(x), q_g(y))$
• $q_{f_2}(f(x, y)) ⟶ f(q_a(x), q_T(y))$
• $q_a(a) ⟶ a$
• $q_T(a) ⟶ a$
• $q_g(g(x)) ⟶ g(q_T(x))$
• $q_T(f(x, y)) ⟶ f(q_T(x), q_T(y))$
• $q_T(g(x)) ⟶ g(q_T(x))$

Bottom-up

$F ≝ \lbrace q_T \rbrace$

$Q ≝ \lbrace q_a, q_f, q_g, q_\bot, q_T \rbrace$

• $f(q_a, q) ⟶ q_f$ for all $q$
• $g(q) ⟶ q_g$ for all $q$
• $f(q_f, q_g) ⟶ q_T$
• $f(q, q’) ⟶ q_\bot$ for all $q, q’ ∈ Q^2 \backslash \Big(\lbrace (q_f, q_g) \rbrace ∪ \lbrace (q_a, q) \mid q ∈ Q \rbrace \Big)$

EX 2: What is recognizable by an FTA?

2. $𝔉 ≝ \lbrace g(1), a(0) \rbrace$ and $L$ the set of ground terms of even height

$Q ≝ \lbrace q \text{ even }, q \text{ odd} \rbrace$

$F ≝ \lbrace q \text{ even} \rbrace$

• $a^{(0)} ⟶ q_{odd}$
• $g(q_{even}) ⟶ q_{odd}$
• $g(q_{odd}) ⟶ q_{even}$

3. $𝔉 ≝ \lbrace f(2), g(1), a(0) \rbrace$ and $L$ the set of ground terms of even height

Not recognizable by any bottom-up tree automaton:

Let $𝒜$ be a NFTA bottom-up, with $n$ states.

The tree $t ≝ f(g^{2n+2}(a), g^{2n+1}(a))$ is recognized.

$r_t$ is the run of $𝒜$ on $t$:

Let’s consider the multi-set \(K ≝ \lbrace \underbrace{r_t(1 1^k)}_{\text{the states reached by going to the right } k+1 \text{ times}} \mid 1 ≤ k ≤ 2n+1 \rbrace\)

By the pigeonhole principle, there exist $k > k’∈ℕ$ such that

\[r_t(1 1^k) = r_t(1 1^{k'})\]

So for any $p∈ℕ$, the tree $t_p ≝ f\big(g^{2n+2}(a), g^{2n+1 + 2p(k-k’)}(a)\big)$ is still recognized, but not in $L$, since $2n+1 + 2p(k-k’) > 2n+2$ and $2n+1 + 2p(k-k’)$ is not even.

Contradiction.

EX 3: Bottom-up vs Top-down

1.

Bottom-up NFTA ⟺ Bottom-up DFTA ⟺ Top-down NFTA > Top-down DFTA

1. Bottom-up NFTA VS Top-down NFTA: just flip around all the arrows of the rewriting rules.

2. Bottom-up DFTA VS Bottom-up NFTA: just do the subset construction.

2.

Bottom-up

to match the pattern:

• $a ⟶ q_a$
• $g(q_a) ⟶ q_g$
• $f(q_a, q_g) ⟶ q_T$

once matched:

• $g(q_T) ⟶ q_T$

• $g(q_g) ⟶ g(q_g)$, $g(q_\bot) ⟶ g(q_g)$

• $f(q, q’) ⟶ q_T$ if $q = q_T$ or $q’ = q_T$
• $f(q, q’) ⟶ q_\bot$ else

3.

By contradiction:

the following trees are accepted:

  graph {
    rankdir=TB;
    f -- a, t;
  }

and

  graph {
    rankdir=TB;
    f -- t, a;
  }

But as the automaton is deterministic, there’s a unique transition $q_f(f(x,y)) ⟶_𝒜 f(q_1(x), q_2(x))$ for both of th previous trees.

So

• $q_1(a), q_2(t)$ are accepted
• $q_1(t), q_2(a)$ are accepted

which means that the following tree must be accepted:

  graph {
    rankdir=TB;
    a1[label="a"];
    f -- a, a1;
  }

which is not true!