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=\left(Q,\Sigma ,\delta ,Q_{0},\alpha \right)$ mit der endlichen Menge der Zustände $Q$, dem Alphabet $A$, der Transitionsfunktion $\delta :Q\times \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 \Sigma$ gilt. In diesem Fall kann die Transitionsfunktion als $\delta :Q\times \Sigma \to Q$ definiert werden.

Sei $w=w_{1}w_{2}w_{3}...$ mit $w_{i}\in \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},...$ 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},...,F_{k}\}$ mit $F_{1}\subseteq F_{2}\subseteq ...\subseteq F_{k}=Q$ oder als eine Partition $\{F_{1},...,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}\neq \emptyset$ 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.