I've started with tree automata. The definition is

(Leaf-to-root) Tree automaton $\mathcal M$ over (nonempty, finite) alphabet $\Sigma$ is quintuple $\mathcal M=(K,\Sigma,\delta,S,F)$ and bound $f$ (the fan-in bound), where $K$ is finite set of states, $S\subseteq K$ set of initial states, $F\subseteq K$set of accepting states with $\delta:A\to K$ for some (nonemty?) $A\subseteq\bigcup\limits_{i=1}^f\underbrace{K\times\cdots\times K}_i\times\Sigma$.

It seems ok to me, but when it comes to an example I'm lost. For example consider following tree automaton over $\{0,1\}$

enter image description here

I suppose $S$ is set of leaves. And now what is example of word $w$ accepted by the automaton? And how is the word read by it?

Thx a lot for help...

  • $\begingroup$ What you drew here is a tree, not a tree-automaton. A tree automaton is has states and transitions, and it reads trees, and "marks" them with its states. Then, a tree is accepted if all the leaves are marked by accepting states. $\endgroup$
    – Shaull
    Commented May 10, 2017 at 14:42
  • $\begingroup$ @Shaull Aaah, here it goes. :) And how is the reading done? I guess it starts with root and using $\delta$ automaton marks the root. And then what? Or am I comletely wrong? $\endgroup$
    – byk7
    Commented May 10, 2017 at 14:52
  • $\begingroup$ Exactly right. The root is marked by the initial state. Then, successors of the root are marked by the state prescribed by the transition function, and so on. $\endgroup$
    – Shaull
    Commented May 10, 2017 at 14:54
  • 2
    $\begingroup$ Tree automata are already described in many resources. I'm not sure it's a good use of anybody's time to write yet another description, in the hope that you'll understand it. Can you be more specific about what it is that you need? $\endgroup$ Commented May 10, 2017 at 21:31


Your Answer

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

Browse other questions tagged or ask your own question.