In der Automatentheorie, einem Teilgebiet der Informatik, ist ein Streett-Automat eine spezielle Form des ω-Automaten.
Streett-Automaten zur Worterkennung
Ein (nicht-)deterministischer Streett-Automat ist ein 5-Tupel wobei gilt: ist eine endliche Menge von Zuständen, die Zustandsmenge ist eine endliche Menge von Symbolen, das Eingabealphabet ist die Übergangsfunktion: im deterministischen Fall mit im nicht-deterministischen Fall mit ist der Startzustand ist eine Familie von Paaren von Zustandsmengen
Dabei bezeichnet die Potenzmenge von .
Akzeptanzverhalten
Ein unendliches Wort wird vom Streett-Automaten akzeptiert genau dann, wenn für einen (deterministisch: den) zugehörigen unendlichen Pfad gilt:
, d. h. falls ein Zustand aus unendlich oft besucht wird, dann wird auch mindestens ein Zustand aus dem zugehörigen unendlich oft besucht.
Alternativ findet sich die äquivalente Akzeptanzbedingung .
Diese Akzeptanzbedingung ist dual zur Akzeptanzbedingung des Rabin-Automaten.
Literatur Erich Grädel, Wolfgang Thomas, Thomas Wilke (Hrsg.): Automata, Logics, and Infinite Games. A Guide to Current Research (= Lecture Notes in Computer Science. Bd. 2500). Springer, Berlin u. a. 2002, ISBN 3-540-00388-6.
Kategorie:Automatentheorie