Streett-Automat

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

In der Automatentheorie, einem Teilgebiet der Informatik, ist ein Streett-Automat eine spezielle Form des ω-Automaten.

Streett-Automaten zur Worterkennung

[Bearbeiten | Quelltext bearbeiten]

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

[Bearbeiten | Quelltext bearbeiten]

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.

  • 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.