Tree automaton
|
|
A tree automaton is a type of finite state machine. Tree automata deal with tree structures, rather than the strings of more conventional finite state machines.
According to how the automata runs on the input tree, it can be of two types (a) top down (b) bottom up.
Top down
Can be described as a
- <math>(Q, \Gamma, q_0, \delta, F).<math>
Here <math>Q<math> is the finite set of states, <math>q_0<math> is the initial state in <math>Q,<math> <math>F<math> is the set of final states and \delta is the transition function.
The automata starts on the root of the tree with the initial state. Reads the symbol and branches into as many states as the number of children. The tree is assumed to be accepted if it is accepted at all the leaves.
Bottom up
Can be described as a
- <math>(Q, \Gamma, q_0, \delta, F).<math>
Here <math>Q<math> is the finite set of states, <math>q_0<math> is the initial state in <math>Q,<math> <math>F<math> is the set of final states and \delta is the transition function.
The automata starts with the initial state simultaneously at all the leaves. According to states of the child and the input symbols the root is labeled with the next state. The tree is accepted if the state labeled at the root is accepting state.