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?


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

  • $\begingroup$ Thanks for your answer. Unfortunately I think I have not understand the idea. So is Q = PxP? . I really need an example please $\endgroup$
    – Marc
    Jun 4, 2019 at 17:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.