Construction of a Deterministic Tree Automaton (DTA)

Question

Let $L \subseteq \Sigma^*$ be a regular language. Let $\Sigma' = \Sigma_0 \cup \Sigma_2$ where $\Sigma_0 =\Sigma$ and $\Sigma_2=\{*\}$.

We define $T_L=\{t \in t_{\Sigma'} \mid \text{The leafs from t are from a word in $L$}\}$ as a tree language.

The task is to construct a DTA for $T_L$.

A DTA A over $\Sigma = \Sigma_0 \cup \cdots \cup \Sigma_m $ is a four tuple with $A= (Q,\Sigma, \delta, F)$ where Q is a finite state set, F final state set, and $\delta : \bigcup _{i=0}^m(Q^i \times \Sigma_i)\rightarrow Q$ and $Q^0 \times \Sigma_0 = \Sigma_0$.

My idea was to set $\Sigma _0 \subseteq L \subseteq \Sigma^*$. But how can the transition function check whether it is a word in L?

Answer 1

Your model is a bottom-up tree automaton. Let $P$ be the set of states of the finite state automaton for regular $L$. Now a state of the tree automaton at a vertex $v$ of the tree contains all $P \times P$ pairs $(p,q)$ such that there is a path from $p$ to $q$ on the string specified by the leaves under $v$. This can be deterministically evaluated in a bottom-up fashion.

More precisely, with every vertex $v$ we associate a binary relation $R(v)$ over $P$, thus $R(v) \subseteq P\times P$. Thus $(p,q)\in R(v)$ iff there is a path from $p$ to $q$ on the leaves under $v$.

For a leaf $v$ labelled $a\in \Sigma$ this means that $R(v) = \{(p,q)\mid (p,a,q) \in \delta\}$, where $\delta$ is the transition relation of the automaton for $L$.

If $u$ is a binary vertex (labelled by $*$) with children $v,w$, then the relation $R(u)$ is the compostition of $R(v)$ and $R(w)$.

We accept at the root $r$ if $R(r)$ contains an accepting pair $(p,q)$ where $p$ is the initial state and $q$ is final.