Baum-Automaten (I)

Literatur: Gecseg/Steinby: Tree Automata (1984), Comon et al.: TATA (Tree automata Techniques and Applications) (2000-), http://www.grappa.univ-lille3.fr/tata/

Definition: Ein Baumautomat A = ($\Sigma$, Q, F, R) besteht aus

• Alphabet A, $\bullet$ Zustandsmenge Q
• Menge der akzeptierenden Zustände F $\subseteq$ Q
• Regelmenge R mit Regeln der Form f (q₁,..., q_k)$\to$q mit f $\in$ $\Sigma$, k$\ge$0, q₁,..., q_k $\in$ Q, q $\in$ Q.

Beispiel: $\Sigma$ = {F, T, $\vee$ , $\wedge$ }, Q = {0, 1}, F = {1},

R = {F$\to$0, T$\to$1, 0 $\vee$ 0$\to$0, 0 $\vee$ 1$\to$1, 1 $\vee$ 0$\to$1, 1 $\vee$ 1$\to$1, 0 $\wedge$ 0$\to$0, 0 $\wedge$ 1$\to$0, 1 $\wedge$ 0$\to$0, 1 $\wedge$ 1$\to$1}.