www.wikidata.de-de.nina.az

Streett Automat In der Automatentheorie einem Teilgebiet der Informatik ist ein eine spezielle Form des ω Automaten en z

Streett-Automat

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

Streett-Automaten zur Worterkennung 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

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.

Literatur 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.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
In der Automatentheorie einem Teilgebiet der Informatik ist ein Streett Automat eine spezielle Form des w Automaten Streett Automaten zur Worterkennung BearbeitenEin nicht deterministischer Streett Automat ist ein 5 Tupel A Q S d q 0 R displaystyle mathcal A left Q Sigma delta q 0 mathcal R right nbsp wobei gilt Q displaystyle Q nbsp ist eine endliche Menge von Zustanden die Zustandsmenge S displaystyle Sigma nbsp ist eine endliche Menge von Symbolen das Eingabealphabet d displaystyle delta nbsp ist die Ubergangsfunktion im deterministischen Fall mit d Q S Q displaystyle delta colon Q times Sigma rightarrow Q nbsp im nicht deterministischen Fall mit d Q S 2 Q displaystyle delta colon Q times Sigma rightarrow 2 Q nbsp q 0 Q displaystyle q 0 in Q nbsp ist der Startzustand R 2 Q 2 Q displaystyle mathcal R subseteq 2 Q times 2 Q nbsp ist eine Familie von Paaren von ZustandsmengenDabei bezeichnet 2 Q displaystyle 2 Q nbsp die Potenzmenge von Q displaystyle Q nbsp Akzeptanzverhalten BearbeitenEin unendliches Wort w a 1 a 2 displaystyle w a 1 a 2 ldots nbsp wird vom Streett Automaten A displaystyle mathcal A nbsp akzeptiert genau dann wenn fur einen deterministisch den zugehorigen unendlichen Pfad p q 0 a 1 q 1 a 2 q 2 displaystyle pi q 0 xrightarrow a 1 q 1 xrightarrow a 2 q 2 ldots nbsp gilt E F R Inf p F Inf p E displaystyle forall E F in mathcal R operatorname Inf pi cap F neq emptyset Rightarrow operatorname Inf pi cap E neq emptyset nbsp d h falls ein Zustand aus F displaystyle F nbsp unendlich oft besucht wird dann wird auch mindestens ein Zustand aus dem zugehorigen E displaystyle E nbsp unendlich oft besucht Alternativ findet sich die aquivalente Akzeptanzbedingung E F R Inf p E Inf p F displaystyle forall E F in mathcal R operatorname Inf pi cap E neq emptyset lor operatorname Inf pi cap F emptyset nbsp Diese Akzeptanzbedingung ist dual zur Akzeptanzbedingung des Rabin Automaten Literatur BearbeitenErich Gradel 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 Abgerufen von https de wikipedia org w index php title Streett Automat amp oldid 200650246