imported>Aka: Tippfehler entfernt, Kleinkram

2024-05-06T18:32:26Z

Neue Seite

Der '''Staiger-Wagner-Automat''' (benannt nach [[Ludwig Staiger]] und [[Klaus Wagner (Informatiker)|Klaus Wagner]]) ist ein [[Omega-Automat|ω-Automat]] und bildet ein Analogon zum [[Muller-Automat]]en. Die von Staiger-Wagner-Automaten erkannten [[Formale Sprache|Sprachen]] sind eine Untermenge der [[ω-reguläre Sprache|ω-regulären]] Sprachen.

== Formale Definition ==

Ein Staiger-Wagner-Automat ist ein 5-Tupel <math>\mathfrak{A} :=\left(Q,\Sigma,q_0,\delta,\mathcal{F}\right)</math> mit
* <math>Q</math> Zustandsmenge
* <math>\Sigma</math> Eingabealphabet
* <math>q_0 \in Q</math> Startzustand
* <math>\delta\colon Q \times \Sigma \to Q</math> Transitionsfunktion.
* <math>\mathcal{F}\subseteq2^Q</math> und <math>\mathcal{F}=\{F_1,..., F_k \}</math> für <math>F_i \subseteq Q</math>

== Eigenschaften ==
<math>\mathfrak{A}</math> akzeptiert <math>\alpha \Longleftrightarrow Occ\left(\rho\right) \in \mathcal{F}</math> (z. B. <math>Occ\left(\rho\right)=F_1</math> oder ... oder <math>Occ\left(\rho\right)=F_k</math>)
gilt für den Lauf <math>\rho</math> von <math>\mathfrak{A}</math> auf dem Wort <math>\alpha</math>.

Eine ω-Sprache ist genau dann ''Staiger-Wagner-erkennbar'', wenn sie eine [[Boolesche Algebra|boolesche]] Kombination von 1-erkennbaren (s. unten) ω-Sprachen ist. Sie ist außerdem Staiger-Wagner-erkennbar, gdw. sie sowohl deterministisch [[Büchi-Automat#Akzeptanzverhalten|Büchi]]-erkennbar als auch deterministisch [[Co-Büchi-Automat|co-Büchi-erkennbar]] ist.

== Beispiel ==
[[Datei:Example for a deterministic Staiger-Wagner automaton.svg|mini|250px|Der zugehörige Automat]]
Sei <math>L:=\{\alpha \in \Sigma^\omega | \alpha\ beinhaltet\ aa\ aber\ kein\ b\}</math> eine ω-Sprache über <math>\Sigma=\{a,b,c\}</math>

Ein deterministischer Staiger-Wagner-Automat, der L erkennt ist dann z. B.: 
<math>\mathfrak{A}_L=\left(Q,\Sigma,q_0,\delta,\mathcal{F}\right)</math> mit
<math>Q=\{1,2,3,4\}, q_0=0, \mathcal{F}=\{\{1,2,3\}\}</math> und 
<math>\delta=\{</math>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<math>\}</math>

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.
=== 1-Akzeptierung ===
Hier gibt es nur eine Menge <math>F</math> akzeptierender Zustände und die Bedingung ist <math>Occ\left(\rho\right)\cap F\neq\emptyset</math>.

=== 1'-Akzeptierung ===
Auch hier gibt es nur eine Menge akzeptierender Zustände und die Bedingung lautet <math>Occ\left(\rho\right)\subseteq F</math>.

== 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: ''[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.48.4015&rep=rep1&type=pdf ω-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 (Informatiker)|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 ==
{{Commonscat}}
[[Kategorie:Automatentheorie]]

Staiger-Wagner-Automat - Versionsgeschichte

imported>Aka: Tippfehler entfernt, Kleinkram