Streett-Automat

In d​er Automatentheorie, e​inem Teilgebiet d​er Informatik, i​st ein Streett-Automat e​ine spezielle Form d​es ω-Automaten.

Streett-Automaten zur Worterkennung

Ein (nicht-)deterministischer Streett-Automat ist ein 5-Tupel ${\displaystyle {\mathcal {A}}=\left(Q,\Sigma ,\delta ,q_{0},{\mathcal {R}}\right)}$ wobei gilt:

• ${\displaystyle Q}$ ist eine endliche Menge von Zuständen, die Zustandsmenge
• ${\displaystyle \Sigma }$ ist eine endliche Menge von Symbolen, das Eingabealphabet
• ${\displaystyle \delta }$ ist die Übergangsfunktion:
  • im deterministischen Fall mit ${\displaystyle \delta \colon Q\times \Sigma \rightarrow Q}$
  • im nicht-deterministischen Fall mit ${\displaystyle \delta \colon Q\times \Sigma \rightarrow 2^{Q}}$
• ${\displaystyle q_{0}\in Q}$ ist der Startzustand
• ${\displaystyle {\mathcal {R}}\subseteq 2^{Q}\times 2^{Q}}$ ist eine Familie von Paaren von Zustandsmengen

Dabei bezeichnet ${\displaystyle 2^{Q}}$ die Potenzmenge von ${\displaystyle Q}$.

Akzeptanzverhalten

Ein unendliches Wort ${\displaystyle w=a_{1}a_{2}\ldots }$ wird vom Streett-Automaten ${\displaystyle {\mathcal {A}}}$ akzeptiert genau dann, wenn für einen (deterministisch: den) zugehörigen unendlichen Pfad ${\displaystyle \pi =q_{0}\;{\xrightarrow {a_{1}}}\;q_{1}\;{\xrightarrow {a_{2}}}\;q_{2}\;\ldots }$ gilt:

${\displaystyle \forall (E,F)\in {\mathcal {R}}:\operatorname {Inf} (\pi )\cap F\neq \emptyset \Rightarrow \operatorname {Inf} (\pi )\cap E\neq \emptyset }$, d. h. falls ein Zustand aus ${\displaystyle F}$ unendlich oft besucht wird, dann wird auch mindestens ein Zustand aus dem zugehörigen ${\displaystyle E}$ unendlich oft besucht.

Alternativ findet sich die äquivalente Akzeptanzbedingung ${\displaystyle \forall (E,F)\in {\mathcal {R}}:\operatorname {Inf} (\pi )\cap E\neq \emptyset \lor \operatorname {Inf} (\pi )\cap F=\emptyset }$.

Diese Akzeptanzbedingung i​st dual z​ur Akzeptanzbedingung d​es 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.