Staiger-Wagner-Automat

Der Staiger-Wagner-Automat (benannt nach Ludwig Staiger und Klaus Wagner) ist ein ω-Automat und bildet ein Analogon zum Muller-Automaten. Die von Staiger-Wagner-Automaten erkannten Sprachen sind eine Untermenge der ω-regulären Sprachen.

Formale Definition

Ein Staiger-Wagner-Automat ist ein 5-Tupel ${\displaystyle {\mathfrak {A}}:=\left(Q,\Sigma ,q_{0},\delta ,{\mathcal {F}}\right)}$ mit

• ${\displaystyle Q}$ Zustandsmenge
• ${\displaystyle \Sigma }$ Eingabealphabet
• ${\displaystyle q_{0}\in Q}$ Startzustand
• ${\displaystyle \delta \colon Q\times \Sigma \to Q}$ Transitionsfunktion.
• ${\displaystyle {\mathcal {F}}\subseteq 2^{Q}}$ und ${\displaystyle {\mathcal {F}}=\{F_{1},...,F_{k}\}}$ für ${\displaystyle F_{i}\subseteq Q}$

Eigenschaften

${\displaystyle {\mathfrak {A}}}$ akzeptiert ${\displaystyle \alpha \Longleftrightarrow Occ\left(\rho \right)\in {\mathcal {F}}}$ (z. B. ${\displaystyle Occ\left(\rho \right)=F_{1}}$ oder ... oder ${\displaystyle Occ\left(\rho \right)=F_{k}}$) gilt für den Lauf ${\displaystyle \rho }$ von ${\displaystyle {\mathfrak {A}}}$ auf dem Wort ${\displaystyle \alpha }$.

Eine ω-Sprache ist genau dann Staiger-Wagner-erkennbar, wenn sie eine boolesche Kombination von 1-erkennbaren (s. unten) ω-Sprachen ist. Sie ist außerdem Staiger-Wagner-erkennbar, gdw. sie sowohl deterministisch Büchi-erkennbar als auch deterministisch co-Büchi-erkennbar ist.

Beispiel

Sei ${\displaystyle L:=\{\alpha \in \Sigma ^{\omega }|\alpha \ beinhaltet\ aa\ aber\ kein\ b\}}$ eine ω-Sprache über ${\displaystyle \Sigma =\{a,b,c\}}$

Ein deterministischer Staiger-Wagner-Automat, der L erkennt ist dann z. B.:
${\displaystyle {\mathfrak {A}}_{L}=\left(Q,\Sigma ,q_{0},\delta ,{\mathcal {F}}\right)}$ mit ${\displaystyle Q=\{1,2,3,4\},q_{0}=0,{\mathcal {F}}=\{\{1,2,3\}\}}$ und
${\displaystyle \delta =\{}$1/a → 2, 1/b → 4, 1/c → 1,
      2/a → 3, 2/b → 4, 2/c → 1,
      3/a → 3, 3/b → 4, 3/c → 3,
      4/a → 4, 4/b → 4, 4/c → 4${\displaystyle \}}$

Genau dann wenn der Automat die Zustände 1, 2 und 3 aber nicht 4 besucht, wird α akzeptiert.

Verwandte Akzeptierungsbedingungen

Mit der Staiger-Wagner-Bedingung sind die beiden folgenden Akzeptierungsbedingungen nahe verwandt.

Transformation in einen Büchi-Automaten

Um einen Staiger-Wagner-Automaten in einen Büchi-Automaten, der dieselbe Sprache erkennt, zu transformieren, werden im Allgemeinen exponentiell viele Zustände gebraucht. Diese Explosion der Zustandsmenge entfällt bei 1-Akzeptanz und 1'-Akzeptanz.

Literatur

• Ludwig Staiger und Klaus W. Wagner, Automatentheoretische und automatenfreie Characterisierungen topologischer Klassen regulärer Folgemengen, Elektronische Informationsverarbeitung und Kybernetik EIK, 10 (1974) 379–392.
• Erich Grädel, Wolfgang Thomas und Thomas Wilke (Herausgeber), Automata, Logics, and Infinite Games, LNCS 2500, 2002, Seite 20 (auf Englisch)
• Ludwig Staiger: ω-Languages. In: Grzegorz Rozenberg, Arto Salomaa (Hrsg.): Handbook of Formal Languages. Band 3: Beyond Words. Springer, Berlin u. a. 1997, ISBN 3-540-60649-1, S. 339–387.
• Wolfgang Thomas: Automata on Infinite Objects. In: Jan van Leeuwen (Hrsg.): Handbook of Theoretical Computer Science. Band B: Formal Models and Semantics. Elsevier Science Publishers u. a., Amsterdam u. a. 1990, ISBN 0-444-88074-7, S. 133–192.

Weblinks

Commons: Staiger-Wagner-Automat – Sammlung von Bildern, Videos und Audiodateien