|
|
|
|
|
Tree AutomatonA 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 (Q, \Gamma, q_0, \delta, F). Here Q is the finite set of states, q_0 is the initial state \in Q, F is the set of final states and \delta is the transition function. The autmata starts on the root of the tree with the intial 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 (Q, \Gamma, q_0, \delta, F). Here Q is the finite set of states, q_0 is the initial state \in Q, F is the set of final states and \delta is the transition function. The autmata starts with the initial state simultaneously at all the leaves. According to states of the child and the input symbols the root is labelled with the next state. The tree is accepted if the state labeled at the root is accepting state. External links See http://www.grappa.univ-lille3.fr/tata
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|