Baum-Automaten (II)

Eine Rechnung von A mit Eingabeterm t ist eine Folge von Regelanwendungen.

Beispiel: Eingabe t = F $\vee$ (T $\wedge$ F), Rechnung F $\vee$ (T $\wedge$ F)$\to$0 $\vee$ (T $\wedge$ F)$\to$0 $\vee$ (1 $\wedge$ F)$\to$0 $\vee$ (1 $\wedge$ 0)$\to$0 $\vee$ 0$\to$ 0.

Eine akzeptierende Rechnung endet mit einem q $\in$ F. Wir schreiben t$\to_{R}^{*}$q $\in$ F.

Die Sprache des Automaten ist L(A) = {t | $\exists$q $\in$ F : t$\to_{R}^{*}$q}.

Die Sprache des Beispiel-Automaten sind genau die Formeln mit Wahrheitswert 1.

Übung: warum gibt es in Baum-Automaten keine Startzustände?

Übung: geben Sie einen Baumautomaten für die Menge aller allgemeingültigen aussagenlogischen Formeln über dem Alphabet {x, T, F,¬, $\vee$ , $\wedge$ } mit einer Variablen x an (Beispiel: x $\vee$ ¬x gehört dazu.) Hinweis: der Automat hat 4 Zustände.