Informatikmaterialien 
von Tino Hempel

Startseite | Informatik | Physik | Mathematik | Sonstiges |

Richard-Wossidlo-Gymnasium Ribnitz-Damgarten
Fachbereich Informatik

Kellerautomat

Grenzen endlicher Automaten

Jeder Taschenrechner beherrscht die Klammerung von Ausdrücken, d. h. zu jeder öffnenden Klammer muss es eine schließende Klammer geben. Dabei müssen sich an jeder beliebigen Stelle der Eingabe stets rechts von der Eingabemarke mehr oder gleich viele öffnende Klammern sein wie schließende Klammern und am Eingabeende gleich viele öffnende und schließende Klammern, sonst wird die Eingabe nicht akzeptiert.

Beispiel: ((3 + 5) / 6) * (10 / ( 24 - 12) + 44) = ?

Wir wollen das Beispiel etwas vereinfachen und überlegen, ob ein Akzeptor die "Klammersprache" erkennen kann. Die Sprache soll L = {ab, aabb, aaabbb, ... } = {anbn | n > 0} sein. Diese Sprache kann als Teil der o. g. Klammersprache gesehen werden.
Für n endlich ist die Umsetzung kein Problem:

Beispiel: n ≤ 3: 

Eine Erweiterung scheint problemlos möglich, man muss nur weitere neue Zustände einführen. Im allgemeinen Fall würde der Automat aber unendlich viele Zustände besitzen müssen. Dies widerspricht aber der Definition des Akzeptors. Es scheint also, dass diese Sprache nicht von einem Akzeptor erkannt werden kann.

Um die Sprache zu erkennen, ist es notwendig, dass sich der Automat irgendwie die Anzahl der n-mal gelesenen Buchstaben merkt. 

Kellerautomaten

1. Speichereinheit

Ein sehr simpler Speicher ist der sog. Kellerspeicher. Wie in einem Keller können Objekte abgelegt (push) und wieder entnommen (pop) werden. Dabei gilt: das zuletzt abgelegte Objekt muss als erstes wieder entnommen werden. Dieses Prinzip bezeichnet man mit Last in – First out (LIFO).

2. Aufbau des Kellerautomaten

Der Automat besitzt einen Kellerspeicher zum Ablegen beliebiger Objekte. Der Kellerspeicher 

Zum Kellerautomaten gehören außerdem eine Steuereinheit und ein Eingabeband, dass die Eingabezeichen und Bandvorbelegungszeichen $ enthält sowie eine Lampe zur Anzeige des Akzeptierzustandes.

Die Steuereinheit kann folgende Speicheroperationen vornehmen:

3. Arbeitsweise:

  1. Initialisierung des Kellerautomaten: Keller ist leer, der Kellerlesekopf steht auf #. 

  2. Einlesen des Eingabezeichens und zerstörendes Einlesen des aktuelle Kellerzeichen. 

  3. Zustandsübergang und Speicheroperation in Abhängigkeit vom aktuellen Zustand, Eingabezeichen und Kellerzeichen

  4. Vorrücken des Eingabelesekopf  um ein Zeichen

  5. ggf. Wiederholung der Schritte 2 bis 4

Der Kellerautomat akzeptiert eine Eingabe, wenn das Eingabewort vollständig eingelesen wurde, der aktuelle Zustand eine Endzustand ist und der Inhalt des Kellers leer ist.

4. Definition

Ein nichtdeterministischer Kellerautomat KA = (X, Z, Γ, δ, z0, k0, ZE)wird durch folgende Angaben definiert :

  • X ist eine nichtleere, endliche Menge – das Eingabealphabet

  • Z ist eine nichtleere, endliche Menge – die Zustandsmenge

  • Γ ist eine nichtleere, endliche Menge – das Kelleralphabet

  • δ ist eine (nicht vollständig definierte) Überführungsfunktion, die ausgehend vom Eingabezeichen, vom Kellerzeichen und vom aktuellen Zustand in einen neuen Zustand bei Ausführung einer Kelleroperation führt 

  • z0 ∈ Z ist der Anfangszustand

  • k0 ∈ Γ ist das Kellervorbelegungszeichen (i. d. R.: #)

  • ZE ⊆ Z ist die Menge der Endzustände

5. Anwendung für die Sprache L = {anbn | n > 0}

Man definiert den Kellerautomaten wie folgt:

X = {a, b}, Z = {q0,q1,q2}, Γ = {#, a}, δ, q0, #, ZE = {q2}

mit der Überführungsfunktion als Graph:

a^nb^n

wobei:

Überführungstabelle:

Zustand Eingabe Kellerzeichen  neuer Zustand Operation
q0 a # | a q0 push a# | aa
q0 b a q1 pop ε
q1 b a q1 pop ε
q1 $ # q2 nop #

zur Startseite		 © Tino Hempel 1997 - 2009 Im Web vertreten seit 1994.
Eine Internet-Seite aus dem Angebot von Tino Hempel.
Für alle Seiten gilt der  Haftungsausschluss/Disclaimer.