# Construction of a Deterministic Tree Automaton (DTA)

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?

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.