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.



Johannes Waldmann 2006-02-02