Advertisement
Published in:
2011 | OriginalPaper | Chapter
Alternierende, endliche Automaten
Authors : Prof. Dr. Martin Hofmann, Prof. Dr. Martin Lange
Published in: Automatentheorie und Logik
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In diesem Kapitel erweitern wir das Konzept des Nichtdeterminismus, welches einen Automaten “raten” lässt, welcher Nachfolgezustand in einer gegebenen Situation gut ist. Dazu führen wir ein duales Konzept ein—das der
universellen Wahl
. Dies lässt einen Automaten raten, welcher Nachfolgezustand in einer gegebenen Situation schlecht ist, d.h. durch welchen Nachfolgezustand sich kein Lauf finden lässt, der akzeptierend ist.
Man kann dies auch als paralleles Berechnungsmodell auffassen. Bei einer universellen Verzweigung werden mehrere Kopien des Automaten erzeugt, die jeweils in verschiedene Nachfolgerzustände übergehen. Von denen müssen alle akzeptieren, damit das vorgelegte Wort insgesamt akzeptiert wird. Auch Nichtdeterminismus kann man als Verzweigung in mehrere Kopien ansehen, von denen aber nur eine akzeptieren muss. Lässt man beide Arten der Verzweigung innerhalb eines Automaten zu, dann spricht man von alternierenden Automaten.