„Rabin-Automat“ – Versionsunterschied
[gesichtete Version] | [gesichtete Version] |
Erweitert |
|||
Zeile 23: | Zeile 23: | ||
* <math>\mathcal{R} \subseteq 2^Q \times 2^Q</math> ist eine Familie von Paaren von Zustandsmengen |
* <math>\mathcal{R} \subseteq 2^Q \times 2^Q</math> ist eine Familie von Paaren von Zustandsmengen |
||
Die Mächtigkeit von <math>\mathcal{R}</math> wird der Index des Automaten bezeichnet. |
Die Mächtigkeit von <math>\mathcal{R}</math> wird der Index des Automaten bezeichnet<ref name=":0">{{Literatur|Autor=Martin Hofmann, Martin Lange|Titel=Automatentheorie und Logik|Hrsg=|Sammelwerk=eXamen.press|Band=|Nummer=|Auflage=|Verlag=Springer-Verlag|Ort=|Datum=2011|Seiten=|ISBN=978-3-642-18089-7}}</ref>. |
||
=== Akzeptanzverhalten === |
=== Akzeptanzverhalten === |
||
Zeile 33: | Zeile 33: | ||
=== Verhältnis zu Büchi-, Streett- und Muller-Automaten === |
=== Verhältnis zu Büchi-, Streett- und Muller-Automaten === |
||
Das Akzeptanzverhalten eines nichtdeterministischen Rabin-Automaten ist allgemeiner als eines Büchi-Automaten, daher gilt: |
Das Akzeptanzverhalten eines nichtdeterministischen Rabin-Automaten (NRA) ist allgemeiner als eines nichtdeterministischen Büchi-Automaten (NBA), daher gilt: |
||
* Für jeden |
* Für jeden NBA der Größe n gibt es einen äquivalenten NRA mit Index 1 und gleicher Größe n.<ref name=":0" /> |
||
Eine Rabinbedingung lässt sich jedoch auch in eine Büchi-Bedingung umwandeln, es gilt: |
Eine Rabinbedingung lässt sich jedoch auch in eine Büchi-Bedingung umwandeln, es gilt: |
||
* Für jeden |
* Für jeden NRA der Größe n und vom Index k gibt es einen äquivalenten NBA mit höchstens <math>n \cdot (k+1)</math> Zuständen.<ref name=":0" /> |
||
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: |
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 |
* Für jeden DRA <math>\mathcal{A}</math> der Größe n und vom Index k gibt es einen deterministischen Streett-Automaten <math>\mathcal\bar{A}</math> der Größe n und vom Index k dessen Sprache komplementär zur Sprache von <math>\mathcal{A}</math> ist: <math>L(\mathcal\bar{A})= \Sigma^\omega \setminus L(\mathcal{A})</math><ref name=":0" /> |
||
== Weblinks == |
== Quellen & Weblinks == |
||
* {{Literatur|Autor=Martin Hofmann, Martin Lange|Titel=Automatentheorie und Logik|Hrsg=|Sammelwerk=eXamen.press|Band=|Nummer=|Auflage=|Verlag=Springer-Verlag|Ort=|Datum=2011|Seiten=|ISBN=978-3-642-18089-7}} |
|||
* [http://home.in.tum.de/~gufler/files/afsb.pdf Vorlesungsmitschrift zu "Automaten, formale Sprachen und Berechenbarkeit", gehalten von Prof. Dr. Markus Holzer, Wintersemester 2004/05] - Kapitel 2.5.3 (PDF-Datei; 461 kB) |
* [http://home.in.tum.de/~gufler/files/afsb.pdf Vorlesungsmitschrift zu "Automaten, formale Sprachen und Berechenbarkeit", gehalten von Prof. Dr. Markus Holzer, Wintersemester 2004/05] - Kapitel 2.5.3 (PDF-Datei; 461 kB) |
||
Version vom 3. Februar 2017, 02:32 Uhr
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 wobei gilt:
- ist eine endliche Menge von Zuständen, die Zustandsmenge
- ist eine endliche Menge von Symbolen, das Eingabealphabet
- ist die Übergangsfunktion mit
- ist der Startzustand mit
- ist eine Familie von Paaren von Zustandsmengen
Die Mächtigkeit von wird der Index des Automaten bezeichnet[1].
Akzeptanzverhalten
Ein unendliches Wort wird vom deterministischen Rabin-Automaten akzeptiert genau dann, wenn es für den zugehörigen unendlichen Pfad ein Paar gibt mit
- , d.h. alle Zustände aus werden nur endlich oft besucht
- , d.h. mindestens ein Zustand aus wird unendlich oft besucht
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.[1]
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 Zuständen.[1]
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 der Größe n und vom Index k dessen Sprache komplementär zur Sprache von ist: [1]
Quellen & Weblinks
- Martin Hofmann, Martin Lange: Automatentheorie und Logik. In: eXamen.press. Springer-Verlag, 2011, ISBN 978-3-642-18089-7.
- Vorlesungsmitschrift zu "Automaten, formale Sprachen und Berechenbarkeit", gehalten von Prof. Dr. Markus Holzer, Wintersemester 2004/05 - Kapitel 2.5.3 (PDF-Datei; 461 kB)
- ↑ a b c d Martin Hofmann, Martin Lange: Automatentheorie und Logik. In: eXamen.press. Springer-Verlag, 2011, ISBN 978-3-642-18089-7.