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 $𝒜=(Q,\mathrm{\Sigma },\mathrm{\Delta },I,ℛ)$ wobei gilt:

• $Q$ ist eine endliche Menge von Zuständen, die Zustandsmenge,
• $\mathrm{\Sigma }$ ist eine endliche Menge von Symbolen, das Eingabealphabet,
• $\mathrm{\Delta }$ ist die Übergangsrelation mit $\mathrm{\Delta }\subseteq Q\times \mathrm{\Sigma }\times Q$,
• $I$ ist eine endliche Menge von Zuständen mit $I\subseteq Q$, die Startzustandsmenge,
• $ℛ\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 $𝒜=(Q,\mathrm{\Sigma },\delta ,q_0,ℛ)$ wobei gilt:

• $Q$ ist eine endliche Menge von Zuständen, die Zustandsmenge,
• $\mathrm{\Sigma }$ ist eine endliche Menge von Symbolen, das Eingabealphabet,
• $\delta$ ist die Übergangsfunktion mit $\delta :Q\times \mathrm{\Sigma }\to Q$,
• $q_0$ ist der Startzustand mit $q_0\in Q$,
• $ℛ\subseteq 2^Q\times 2^Q$ ist eine Familie von Paaren von Zustandsmengen.

Die Mächtigkeit von $ℛ$ wird als Index des Automaten bezeichnet.

Akzeptanzverhalten

Ein unendliches Wort $w=a_1{a}_2\dots$ wird vom deterministischen Rabin-Automaten $𝒜$ akzeptiert genau dann, wenn es für den zugehörigen unendlichen Pfad $\pi =q_0\stackrel{a_1}{\to }{q}_1\stackrel{a_2}{\to }{q}_2\dots$ ein Paar $(L,U)\in ℛ$ gibt mit

• $\mathrm{Inf}(\pi )\cap L=\mathrm{\varnothing }$, d. h. alle Zustände aus $L$ werden nur endlich oft besucht, und
• $\mathrm{Inf}(\pi )\cap U\ne \mathrm{\varnothing }$, 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 $𝒜$ der Größe n und vom Index k gibt es einen deterministischen Streett-Automaten $\overline{𝒜}$ der Größe n und vom Index k dessen Sprache komplementär zur Sprache von $𝒜$ ist: $L(\overline{𝒜})={\mathrm{\Sigma }}^{\omega }\setminus L(𝒜)$.

Des Weiteren gilt:

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

Quellen und Weblinks

• Vorlage:Literatur
• Vorlesungsmitschrift zu "Automaten, formale Sprachen und Berechenbarkeit", gehalten von Prof. Dr. Markus Holzer, Wintersemester 2004/05 – Kapitel 2.5.3 (PDF; 461 kB)