Download Endbericht

18
2.1.2.1.1.2
KAPITEL 2. SEMINARPHASE
Lauf Man kann auch anders als durch die Move-Relation herausfinden,
ob ein Term von einem Baumautomaten akzeptiert wird. Anstatt Zustände in den Baum
einzufügen und sie dann zu verschieben, kann man auch von den Blättern angefangen
jeden Teilterm oder jede Konstante aus einem Knoten auf einen Zustand abbilden.
Definition Sei t ein Grundterm und A ein NTFA. Ein Lauf r auf A über t ist eine Abbildung
r : P os(t) → Q (wobei P os(t) die Position von t bezeichnet, welches sowohl eine Konstante
als auch eine mehrstellige Funktion sein kann) passend zu 4.
Der NTFA beginnt an den Blättern und bewegt sich nach oben, wobei er entlang seines
Weges jede Position des Terms, die er bei einem Knoten findet, auf einen Zustand abbildet,
bis zur Wurzel. Der Baum, bzw. der Term, wird akzeptiert, wenn nach dem Lauf an der
Wurzel ein akzeptierender Zustand steht.
Beispiel Sei F
= {or(, ), and(, ), not(), 0, 1}.Wir betrachten den Automaten A =
(Q, F, Qf , 4) definiert durch:
Q = {q0 , q1 }, Qf = {q1 } und
4 = {0 → q0 , 1 → q1 , not(q0 ) → q1 , not(q1 ) → q0 , and(q0 , q0 ) → q0 , and(q0 , q1 ) → q0 } ∪
{and(q1 , q0 ) → q0 , and(q1 , q1 ) → q1 , or(q0 , q0 ) → q0 , or(q0 , q1 ) → q1 } ∪
{or(q1 , q0 ) → q1 , or(q1 , q1 ) → q1 }
Gegeben sei der Grundterm t = and(not(or(0, 1)), or(1, not(0)), mit dem dazugehörigen