Rabin-Automat

Der Rabin-Automat ist eine spezielle Form des ω-Automaten.

Rabin-Automaten zur Worterkennung

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
• Σ ist eine endliche Menge von Symbolen, das Eingabealphabet
• δ ist die Übergangsfunktion mit $\delta: Q \times \Sigma \rightarrow Q$
• q₀ ist der Startzustand mit $q_0 \in Q$
• $\mathcal{R} \subseteq 2^Q \times 2^Q$ ist eine Familie von Paaren von Zustandsmengen

Akzeptanzverhalten

Ein unendliches Wort $w=a_1a_2 \ldots$ wird vom deterministischen Rabin-Automaten $\mathcal{A}$ akzeptiert genau dann, wenn es für den zugehörigen unendlichen Pfad $\pi = q_0 \; \begin{matrix} {}_{a_1} \\ \rightarrow \\ \,\end{matrix} \; q_1 \; \begin{matrix} {}_{a_2} \\ \rightarrow \\ \,\end{matrix} \; q_2 \; \ldots$ ein Paar $(L, U) \in \mathcal{R}$ gibt mit

• $\inf(\pi) \cap L = \emptyset$, d.h. alle Zustände aus L werden nur endlich oft besucht
• $\inf(\pi) \cap U \neq \emptyset$, d.h. mindestens ein Zustand aus U wird unendlich oft besucht

Weblinks

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