Fachrat Informatik - Forum

Quoted

Original von MAX
Ich habe mein Problem mit der Definition von AEA. Genauer verstehe ich nicht, wie die Überführungsfunktion bzw. erweiterte Überführungsfunktion funktioniert. Zweitens ist es mir nicht klar, welche Sprache dieser Automat akzeptiert.

Die Definition in der Aufgabe fand ich auch etwas dürftig, zumal dort nicht angegeben ist, wie man sich einen Rechenschritt (also einen Konfigurationsübergang) eines solchen Automaten vorzustellen hat. Zudem ist auch nicht klar, was eine Konfiguration eines AEA sein soll. Aus der Defintion habe ich mir folgendes Modell entwickelt:

B^Z ist ja die Menge aller Abbildungen von Z nach {0, 1}. Betrachtet man nun ein Element f aus B^Z, so ist {z \in Z | f(z) = 1} die Menge der Zustände, die durch f auf 1 abgebildet werden. Alle anderen Zustände werden demnach durch f auf 0 abgebildet. Somit läßt sich jedes Element von B^Z als eine Teilmenge von Z auffassen. In dieser Sichtweise entspricht B^Z der Potenzmenge von Z, nennen wir sie im folgenden P(Z).

Die Überführungsfunktion delta eines AEA bildet jedes Tripel von Zustand, Zeichen und B^Z-Abbildung nach {0, 1} ab. Dies läßt sich auch anders definieren. Betrachten wir die neue Überführungsfunktion gamma : Z x Sigma -> P(P(Z)). Dazu definieren wir
gamma(z, a) := {f \in B^Z | delta(z, a, f) = 1}. Das f in dieser Definition fassen wir dabei als Menge von Zuständen wie oben beschrieben auf.

Damit legt die Überführungsfunktion für jeden Zustand und jedes Eingabezeichen eine Menge von Zustandsmengen fest. Vom Prinzip her ist das wie bei NEAs, dort wird allerdings jeder Kombination aus Zustand und Eingabezeichen nur ein einzelner Folgezustand zugeordnet, anstatt wie hier eine Menge.

Eine Konfiguration eines AEA besteht damit aus einer Menge von Zuständen (anstatt wie bei NEAs/DEAs aus einem einzelnen Zustand) und dem noch zu lesenden Rest des Eingabewortes.

Die Startkonfiguration ist die Menge {z0} zusammen mit dem kompletten Eingabewort.

Ein Rechenschritt eines AEA läßt sich dann wie folgt auffassen: Ist der AEA in der Zustandsmenge D und liest das Zeichen a, so gibt es eine Menge von Zustandsmengen, die von jedem Zustand in D erreichbar sind. Ist D = {d1, d2, ..., dn}, so ist diese Menge gegeben durch
{gamma(d1, a)} n {gamma(d2, a)} n ... n {gamma(dn, a)}.
In jeden Zustandsmenge aus dieser Menge kann der AEA nun durch einen Rechenschritt überwechseln. Dies tut er nichtdeterministisch.

Ein AEA akzeptiert seine Eingabe genau dann, wenn es einen nichtdeterministischen Rechenpfad gibt, so daß am Ende der Rechnung als Zustandmenge genau die Menge der Endzustände angenommen wurde.

Mit diesem Modell ist nun auch klar, wie die Aufgabe 11.2 anschaulich gelöst werden kann. Es gibt 2^N Zustandsmengen, in denen sich der AEA befinden kann. Ordnen wir jeder dieser Mengen einen einzelnen Zustand in einem NEA zu und definieren die Übergänge entsprechend gamma, so erhalten wir einen zum AEA äquivalenten NEA mit 2^N Zuständen. Aus der Grundlagenvorlesung ist bekannt, daß sich jeder NEA mit k Zuständen in einen äquivalenten DEA mit 2^k Zuständen umformen läßt. Machen wir dies hier, so erhalten wir einen DEA mit 2^{2^N} Zuständen. Fertig.

PS: Alternierende endliche Automaten sind wohl von Konzept her mit alternierenden Turingmaschinen verwandt. Ich habe zwar mittlerweile eine Idee, wie man sich eine solche Alternation zusammen mit der Defintition in Aufgabe 11.2 vorzustellen hat, dies ist aber ziemlich kompliziert und möchte ich lieber nicht aufschreiben. AEAs sind für die Klausur (schätze ich mal) sowieso nicht von großem Interesse.