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 ${\displaystyle A=\left(Q,\Sigma ,\delta ,Q_{0},\alpha \right)}$ mit der endlichen Menge der Zustände ${\displaystyle Q}$, dem Alphabet ${\displaystyle A}$, der Transitionsfunktion ${\displaystyle \delta :Q\times \Sigma \to P(Q)}$, der Menge der Startzustände ${\displaystyle Q_{0}\subseteq Q}$ und einer Akzeptanzkomponente ${\displaystyle \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 ${\displaystyle |Q_{0}|=1}$ und ${\displaystyle |\delta (q,\sigma )|=1}$ für alle ${\displaystyle q\in Q}$ und ${\displaystyle \sigma \in \Sigma }$ gilt. In diesem Fall kann die Transitionsfunktion als ${\displaystyle \delta :Q\times \Sigma \to Q}$ definiert werden.

Sei ${\displaystyle w=w_{1}w_{2}w_{3}...}$ mit ${\displaystyle w_{i}\in \Sigma }$ für alle ${\displaystyle i\in \mathbb {N} }$ ein unendliches Wort. Ein Lauf ${\displaystyle r}$ für ${\displaystyle w}$ ist eine unendliche Folge ${\displaystyle q_{0},q_{1},q_{2},...}$ mit ${\displaystyle q_{0}\in Q_{0}}$ und ${\displaystyle q_{i+1}\in \delta (q_{i},w_{i+1})}$ für alle ${\displaystyle i\in \mathbb {N} _{0}}$. Dabei ist ${\displaystyle inf(r)}$ die Menge aller unendlich oft in ${\displaystyle r}$ vorkommenden Zustände.

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

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

Ein Wort wird dann akzeptiert, wenn dafür ein Lauf ${\displaystyle r}$ existiert, bei dem das minimale ${\displaystyle i\in \mathbb {N} }$ mit ${\displaystyle 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.

Einzelnachweise

1. ↑ Andrzej Włodzimierz Mostowski: Regular expressions for infinite trees and a standard form of automata. Springer, doi:10.1007/3-540-16066-3_15. 
2. ↑ Berndt Farwer: ω-Automata. 2002, S. 10, doi:10.1007/3-540-36387-4_1. 
3. ↑ Nir Piterman: From Nondeterministic Büchi and Streett Automata to Deterministic Parity Automata. 2007, S. 5, doi:10.48550/arXiv.0705.2205. 
4. 1 2 3 Orna Kupferman: Automata Theory and Model Checking. In: Edmund Clarke, Thomas Henzinger, Helmut Veith, Roderick Bloem (Hrsg.): Handbook of Model Checking. Springer, 2018, S. 122 ff., doi:10.1007/978-3-319-10575-8_4. 
5. ↑ Carsten Fritz: Simulation-based simplification of omega-automata. 2005, S. 117.