Rabin-Automat
# Rabin-Automat

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 ${\mathcal {A}}=\left(Q,\Sigma ,\Delta ,I,{\mathcal {R}}\right)$ wobei gilt:

* $Q$ ist eine endliche Menge von Zuständen, die Zustandsmenge,
* $\Sigma$ ist eine endliche Menge von Symbolen, das Eingabealphabet,
* $\Delta$ ist die Übergangsrelation mit $\Delta \subseteq Q\times \Sigma \times Q$,
* $I$ ist eine endliche Menge von Zuständen mit $I\subseteq Q$, die Startzustandsmenge,
* ${\mathcal {R}}\subseteq 2^{Q}\times 2^{Q}$ ist eine Familie von Paaren von Zustandsmengen.

### Deterministischer Rabin-Automat zur Worterkennung

Ein deterministischer Rabin-Automat (DRA) ist ein 5-Tupel ${\mathcal {A}}=\left(Q,\Sigma ,\delta ,q_{0},{\mathcal {R}}\right)$ wobei gilt:

* $Q$ ist eine endliche Menge von Zuständen, die Zustandsmenge,
* $\Sigma$ ist eine endliche Menge von Symbolen, das Eingabealphabet,
* $\delta$ ist die Übergangsfunktion mit $\delta \colon Q\times \Sigma \rightarrow Q$,
* $q_{0}$ ist der Startzustand mit $q_{0}\in Q$,
* ${\mathcal {R}}\subseteq 2^{Q}\times 2^{Q}$ ist eine Familie von Paaren von Zustandsmengen.

Die Mächtigkeit von ${\mathcal {R}}$ wird als Index des Automaten bezeichnet.

### Akzeptanzverhalten

Ein unendliches Wort $w=a_{1}a_{2}\ldots$ wird vom deterministischen Rabin-Automaten ${\mathcal {A}}$ akzeptiert genau dann, wenn es für den zugehörigen unendlichen Pfad $\pi =q_{0}\;{\xrightarrow {a_{1}}}\;q_{1}\;{\xrightarrow {a_{2}}}\;q_{2}\;\ldots$ ein Paar $(L,U)\in {\mathcal {R}}$ gibt mit

* $\operatorname {Inf} (\pi )\cap L=\emptyset$, d. h. alle Zustände aus $L$ werden nur endlich oft besucht, und
* $\operatorname {Inf} (\pi )\cap U\neq \emptyset$, d. h. mindestens ein Zustand aus $U$ wird unendlich oft besucht.

Eine Definition mit umgekehrter Bedeutung des Paars $(L,U)$ 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 $n\cdot (k+1)$ 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 ${\mathcal {A}}$ der Größe n und vom Index k gibt es einen deterministischen Streett-Automaten ${\overline {\mathcal {A}}}$ der Größe n und vom Index k dessen Sprache komplementär zur Sprache von ${\mathcal {A}}$ ist: $L({\overline {\mathcal {A}}})=\Sigma ^{\omega }\setminus L({\mathcal {A}})$.

Des Weiteren gilt:

* Jeder DRA ist zu einem deterministischen Muller-Automaten (DMA) äquivalent und umgekehrt.

## Quellen und Weblinks

* Martin Hofmann, Martin Lange: Automatentheorie und Logik. In: eXamen.press. Springer-Verlag, 2011, ISBN 978-3-642-18089-7.
* Vorlesungsmitschrift zu "Automaten, formale Sprachen und Berechenbarkeit", gehalten von Prof. Dr. Markus Holzer, Wintersemester 2004/05 – Kapitel 2.5.3 (PDF; 461 kB)
