Streett-Automat

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 deterministischen Streett-Automaten akzeptiert genau dann, wenn für 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[Bearbeiten | Quelltext bearbeiten]

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