Suche Home Einstellungen Anmelden Hilfe

3.2.2 Nicht-Deterministische Kellerautomaten

Konfigurationsübergang Wie "fühlt" sich ein Kellerautomat von innen an? Auf welche Informationen hat er Zugriff? Ein Javaapplet gibt Ihnen einen Einblick in die Innenwelt eines KA.

Man kann den KA als Erweiterung eines Endlichen Automaten verstehen. Zusätzlich hinzugekommen ist der Keller, der in der Definition erfasst werden muss. Ein KA kann durch ein 7-Tupel beschrieben werden. Genau wie beim EA kann der Automat verschiedene Zustände aus einer Menge von Zuständen einnehmen. Es gibt einen ausgezeichneten Startzustand aus der Menge der Zustände. Die Zustände, in denen der Automat seine Analyse beenden kann - die Endzustände, bilden eine Teilmenge aus der Menge der Zustände. Desweiteren ist das Eingabealphabet festgelegt. Im Keller können die Symbole des Kelleralphabets stehen. Mit dem ausgezeichneten Symbol Z0 wird die unterste Zelle markiert. Durch den Keller ist die Übergangsfunktion komplexer als beim EA. Der aktuelle Zustand, das aktuelle Symbol der Eingabe und das aktuelle Kellersymbol (der Inhalt der obersten Kellerzelle) fließen in die Bestimmung der Folgekonfiguration ein. Der Lesekopf wird bei einem "" nicht verschoben. In diesem Fall wird statt dem tatsächlichen Eingabesymbol das leere Wort als aktuelle Eingabe angenommen. Der Nichtdeterminismus folgt aus der Definition der Übergangsfunktion. Für ein Tripel kann es mehrere Folgezustände mit unterschiedlichen Aktionen geben.

Einführung 1   2   3   4   5   6 Übergänge

Benutzer: Gast • Besitzer: senn • Zuletzt geändert am: