Ω-Automat

Ω-Automat

Ein ω-Automat (Omega-Automat) ist ein mathematisches Modell, das eine Erweiterung des endlichen Automaten auf die Eingabe unendlicher Wörter darstellt. Endlich heißt der Automat deshalb, weil die Anzahl seiner inneren Zustände endlich ist. Ebenso ist das Alphabet, über dem dieser Automat arbeitet, endlich.

Der griechische Buchstabe ω (omega) steht hier für die kleinste unendliche Ordinalzahl.

Motiviert wird die Betrachtung solcher Automaten durch viele Systeme (zum Beispiel Betriebssysteme), die per Definition eigentlich nicht terminieren sollen, sondern unendlich lange betrieben werden.

Inhaltsverzeichnis

Beschreibung

Ausgehend von einem besonderen Zustand (Startzustand) liest der ω-Automat eine unendlich abzählbare Folge von Symbolen (Eingabewort), die Elemente einer endlichen Menge von Symbolen (Eingabealphabet) sind.

Dabei geht der ω-Automat schrittweise vor, wobei in jedem Schritt das jeweils nächste Symbol des Eingabewortes gelesen wird. Den Folgezustand bestimmt die Zustandsübergangsfunktion δ in Abhängigkeit vom aktuell gelesenen Zeichen und dem momentanen Zustand.

Die Frage, ob das Eingabewort akzeptiert wird, ist von der Art des ω-Automaten abhängig. In jedem Fall wird die Menge der Zustände zu Rate gezogen, die unendlich oft durchlaufen werden.

Darstellung

Ein ω-Automat lässt sich sowohl als Zustandsdiagramm als auch als Zustandstabelle darstellen:

Beispiel für einen DEA
a b
s0 s0 s1
s1 s0 s2
s2 s1 s2
Zustandsdiagramm Zustandstabelle

Das Diagramm liest sich wie folgt:

  • Einfache Kreise stellen Zustände dar.
  • Im Kreis steht der Name des Zustands bzw. der Zustand.
  • Pfeile stellen Transitionen dar. An den Pfeilen steht, welches Zeichen (oder gar welche Wörter) der Automat bei der Transition liest.
  • Der Anfangszustand ist dadurch gekennzeichnet, dass er Endpunkt eines Pfeils ist, der keinen Zustand als Ausgangspunkt hat.
  • Endzustände sind durch doppelte Kreise gekennzeichnet (aber nicht bei allen Typen des ω-Automaten gibt es Endzustände; die Akzeptanzmechanismen sind unterschiedlich).

Typen

Wie bei den endlichen Automaten unterscheidet man auch bei den ω-Automaten zwischen deterministischen und nichtdeterministischen Automaten.

Weiterhin unterscheidet man die Automaten nach der Art, wie entschieden wird, ob ein eingegebenes Wort akzeptiert wird oder nicht. Diese Akzeptanz eines Wortes entscheidet sich in den meisten Fällen nach den unendlich oft angenommenen Zuständen. Beispiele für ω-Automaten sind der Büchi-Automat, der Muller-Automat, der Rabin-Automat, der Streett-Automat und der Parity-Automat.

Außer dem deterministischen Büchi-Automaten erkennen alle genannten Automaten die Klasse der ω-regulären Ausdrücke (die Erweiterung der regulären Ausdrücke auf unendliche Zeichenfolgen). Der deterministische Büchi-Automat erkennt nur eine Teilmenge dieser Ausdrücke und stellt eine echt schwächere Automatenklasse dar.

Formale Definition

Ein ω-Automat ist ein 5-Tupel:

M = (Σ,Z,Z0,δ,ZE)

Dabei sind die Elemente wie folgt definiert:

  • Σ ist eine endliche Menge, das Eingabealphabet, aus dessen Elementen die eingegebenen Wörter zusammengesetzt sind
  • Z Ist die zu Σ disjunkte endliche Menge der Zustände des Automaten
  • Z_0 \in Z ist der Startzustand
  • \delta : \Sigma \times Z \rightarrow Z ist die Überführungsfunktion, sie ist gewöhnlich total, d.h. jedes Element der Urbildmenge \Sigma \times Z hat ein Bild. (Mathematiker unterscheiden dies gewöhnlich nicht, für sie ist jede Funktion per Definition total.)
  • ZE - Ist eine vom Automatentyp abhängige Komponente, die regelt, wann ein Wort akzeptiert wird, bei Büchi-Automaten zum Beispiel ist dies eine Teilmenge von Z

Bei nichtdeterministischen Automaten wird die Überführungsfunktion als \delta : \Sigma \times Z \rightarrow P(Z) definiert, wobei P(Z) die Potenzmenge von Z ist. Der Automat kann dann bei der Eingabe eines neuen Zeichens nichtdeterministisch in einen von mehreren Zuständen gehen, die durch das Bild (Menge von Zuständen) der Funktion gegeben werden.

Siehe auch


Wikimedia Foundation.

Игры ⚽ Нужна курсовая?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • automat — AUTOMÁT, Ă, automaţi, te, adj., s.n. 1. adj. (Despre aparate, maşini etc.) Care este acţionat printr un dispozitiv mecanic; (despre anumite operaţii; adesea adverbial) care se efectuează prin acţiunea unui dispozitiv mecanic. ♢ Armă automată (şi… …   Dicționar Român

  • Automat Pictures — is an entertainment production company based in Los Angeles, which specializes in EPK/DVD Added Value, as well original television programming and independent feature documentary production. Automat has contributed content for many DVDs, among… …   Wikipedia

  • Automat — Sm erw. fach. (16. Jh.) Entlehnung. Entlehnt aus l. automatus, automatos Adj. aus eigenem Antrieb handelnd, freiwillig , n. Maschine, die sich selbst bewegt , zu gr. autómatos aus eigenem Antrieb, von selbst geschehend , zu gr. autós selbst (auto …   Etymologisches Wörterbuch der deutschen sprache

  • automat — {{/stl 13}}{{stl 8}}rz. mnż I, D. u, Mc. automatacie {{/stl 8}}{{stl 20}} {{/stl 20}}{{stl 12}}1. {{/stl 12}}{{stl 7}} urządzenie mechaniczne o własnym napędzie, przeznaczone do samoczynnego wykonywania określonej pracy : {{/stl 7}}{{stl… …   Langenscheidt Polski wyjaśnień

  • automat — autòmāt m <G automáta> DEFINICIJA 1. tehn. uređaj koji samostalno obavlja koristan rad, skraćuje broj radnji ili radni proces bez izravnog sudjelovanja čovjeka u svakoj radnji, ali prema njegovoj zamisli [automat za kavu (čaj, čokoladu,… …   Hrvatski jezični portal

  • automat — n. 1. a vending machine from which you can get food. [WordNet 1.5] 2. a type of cafeteria where food is served from machines. [WordNet 1.5] …   The Collaborative International Dictionary of English

  • Automat — Automat. Eine künstliche Maschine, welche ihren Mechanismus in sich verborgen hält, und sich von selbst zu bewegen scheint. Schon seit mehrern Jahrhunderten hat man sich damit abgegeben und besonders Uhren gemacht, an welchen allerlei Spielwerke… …   Damen Conversations Lexikon

  • autòmāt — m 〈G automáta〉 1. {{001f}}tehn. uređaj koji samostalno obavlja koristan rad, skraćuje broj radnji ili radni proces bez izravnog sudjelovanja čovjeka u svakoj radnji, ali prema njegovoj zamisli [∼ za kavu (čaj, čokoladu, osvježavajuće piće)] 2.… …   Veliki rječnik hrvatskoga jezika

  • Autŏmat — (v. gr.), 1) eigentlich was von selbst geschieht, bes. was sich von selbst bewegt; daher 2) Maschine, die sich ohne äußere Hülfe durch in derselben angebrachte Räder, Federn u. Gewichte bewegt. Eigentlich sind alle Arten Uhrwerke, Planetarien u.… …   Pierer's Universal-Lexikon

  • Automat — (griech., »Selbstbeweger«), im weitern Sinne jede durch verborgene Kraftmittel (Federn, Gewichte, Elektromagnetismus) in Bewegung gesetzte Vorrichtung (Uhren, Planetarien), im engern Sinn eine Vorrichtung, welche die Tätigkeit eines Menschen… …   Meyers Großes Konversations-Lexikon

  • Automat [1] — Automat (Destillierapparat von Ilges), s. Spiritusfabrikation …   Lexikon der gesamten Technik

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”