Der Rabin-Automat ist eine spezielle Form des ω-Automaten. Sie sind benannt nach ihrem Erfinder Michael O. Rabin, der damit 1969 erstmals endliche Automaten auf unendliche Wörter verallgemeinerte.
Rabin-Automaten zur Worterkennung
Nichtdeterministischer Rabin-Automat zur Worterkennung
Ein nichtdeterministischer Rabin-Automat (NRA) 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 Übergangsrelation mit , ist eine endliche Menge von Zuständen mit , die Startzustandsmenge, ist eine Familie von Paaren von Zustandsmengen.
Deterministischer Rabin-Automat zur Worterkennung
Ein deterministischer Rabin-Automat (DRA) 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 mit , ist der Startzustand mit , ist eine Familie von Paaren von Zustandsmengen.
Die Mächtigkeit von wird als Index des Automaten bezeichnet.
Akzeptanzverhalten
Ein unendliches Wort wird vom deterministischen Rabin-Automaten akzeptiert genau dann, wenn es für den zugehörigen unendlichen Pfad ein Paar gibt mit , d. h. alle Zustände aus werden nur endlich oft besucht, und , d. h. mindestens ein Zustand aus wird unendlich oft besucht. Eine Definition mit umgekehrter Bedeutung des Paars ist ebenso möglich.
Verhältnis zu Büchi-, Streett- und Muller-Automaten Das Akzeptanzverhalten eines nichtdeterministischen Rabin-Automaten (NRA) ist allgemeiner als eines nichtdeterministischen Büchi-Automaten (NBA), daher gilt: Für jeden NBA der Größe n gibt es einen äquivalenten NRA mit Index 1 und gleicher Größe n. Durch verallgemeinerte Potzenautomatenkonstruktion lässt sich zeigen, dass: Zu jedem NBA gibt es einen DRA mit identischer Sprache. Eine Rabinbedingung lässt sich jedoch auch in eine Büchi-Bedingung umwandeln, es gilt: Für jeden NRA der Größe n und vom Index k gibt es einen äquivalenten NBA mit höchstens Zuständen. Die Akzeptanzbedingung des Rabin-Automaten ist dual zur Akzeptanzbedingung des Streett-Automaten. Daher lassen sich Deterministische Rabin- und Streett-Automaten leicht ineinander komplementieren und es gilt: Für jeden DRA der Größe n und vom Index k gibt es einen deterministischen Streett-Automaten der Größe n und vom Index k dessen Sprache komplementär zur Sprache von ist: . Des Weiteren gilt: Jeder DRA ist zu einem deterministischen Muller-Automaten (DMA) äquivalent und umgekehrt.
Quellen und Weblinks
Vorlesungsmitschrift zu "Automaten, formale Sprachen und Berechenbarkeit", gehalten von Prof. Dr. Markus Holzer, Wintersemester 2004/05 – Kapitel 2.5.3 (PDF; 461 kB)
Einzelnachweise
Kategorie:Automatentheorie
en:Rabin automaton