# 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.

# 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.

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!

Tags:

Updated: