Paritätsautomat

Der Paritätsautomat, auch Parity-Automat, ist in der Automatentheorie ein Automat, der auf unendlichen Wörtern arbeitet. Er ist eine Variante des ω-Automaten. Die von Paritätsautomaten erkannten Sprachen sind die ω-regulären Sprachen. Eingeführt wurde er 1984 von Andrzej Włodzimierz Mostowski.

Definition

Ein Paritätsautomat ist definiert als ein 5-Tupel $A=(Q,\mathrm{\Sigma },\delta ,Q_0,\alpha )$ mit der endlichen Menge der Zustände $Q$, dem Alphabet $A$, der Transitionsfunktion $\delta :Q\times \mathrm{\Sigma }\to P(Q)$, der Menge der Startzustände $Q_0\subseteq Q$ und einer Akzeptanzkomponente $\alpha$, für die es verschiedene Definitionen gibt. Weil die Transitionsfunktion auf die Potenzmenge abbildet, ist der Automat nichtdeterministisch. Ein Paritätsautomat ist deterministisch, wenn $|Q_0|=1$ und $|\delta (q,\sigma )|=1$ für alle $q\in Q$ und $\sigma \in \mathrm{\Sigma }$ gilt. In diesem Fall kann die Transitionsfunktion als $\delta :Q\times \mathrm{\Sigma }\to Q$ definiert werden.

Sei $w=w_1{w}_2{w}_3\dots$ mit $w_i\in \mathrm{\Sigma }$ für alle $i\in \mathbb{N}$ ein unendliches Wort. Ein Lauf $r$ für $w$ ist eine unendliche Folge $q_0,q_1,q_2,\dots$ mit $q_0\in Q_0$ und $q_{i+1}\in \delta (q_i,w_{i+1})$ für alle $i\in {\mathbb{N}}_0$. Dabei ist $\inf (r)$ die Menge aller unendlich oft in $r$ vorkommenden Zustände.

Die Akzeptanzkomponente $\alpha$ kann als Prioritätsfunktion $p:Q\to \mathbb{N}$ definiert werden. Ein Wort wird dann akzeptiert, wenn dafür ein Lauf $r$ existiert, bei dem $\min \{p(q)|q\in \inf (r)\}$ gerade ist. Alternativ kann auch gefordert werden, dass $\max \{p(q)|q\in \inf (r)\}$ gerade ist.

Die Akzeptanzkomponente $\alpha$ kann auch als Menge $\{F_1,\dots ,F_k\}$ mit $F_1\subseteq F_2\subseteq \dots \subseteq F_k=Q$ oder als eine Partition $\{F_1,\dots ,F_k\}$ von $Q$ für eine Zahl $k\in \mathbb{N}$, die Index des Automaten genannt wird, definiert werden.

Ein Wort wird dann akzeptiert, wenn dafür ein Lauf $r$ existiert, bei dem das minimale $i\in \mathbb{N}$ mit $\inf (r)\cap F_i\ne \mathrm{\varnothing }$ gerade ist.

Eigenschaften

Deterministische und nichtdeterministische Paritätsautomaten besitzen die gleiche Ausdrucksstärke. Die von ihnen erkannten Sprachen sind die ω-regulären Sprachen. Sie sind somit äquivalent zu nichtdeterministischen Büchi-Automaten sowie deterministischen und nichtdeterministischen Rabin-, Streett-, Muller- und Generalisierten Büchi-Automaten.

Ein Paritätsautomat kann allein durch Änderung der Akzeptanzkomponente in äquivalente Rabin-, Streett- und Muller-Automaten überführt werden.

Ein Büchi-Automat kann als Paritätsautomat, dessen Prioritätsfunktion nur auf 0 und 1 abbildet, betrachtet werden.