Index

Wahlpflichtthemen

1. Automaten (5)


Keller-Automaten

Gesucht ist zum Ausdruck a = anbn mit n Î N0 ein erkennender Automat.

Offensichtlich ist der folgende Automat unbrauchbar:
Automat zu a*b* Er stellt den regulären Ausdruck a = a*b* dar, d.h. eine beliebige Anzahl a gefolgt von einer nicht notwendigerweise gleichen beliebigen Anzahl b. Im ursprünglichen Ausdruck muss aber die Anzahl der a und der nachfolgenden b gleich groß sein, also z.B. ab, aabb, aaabbb, aaaabbbb usw.
Der zugehörige Automat müsste sich etwa so aufbauen:
Nicht endlicher Automat
Dies ist aber kein endlicher Automat. Daher kann die Sprache dieses regulären Ausdrucks mit den bisherigen endlichen Automaten nicht erkannt werden. Dies liegt daran, dass ein endlicher Automat nicht beliebig viele Zustände haben kann.

Man muss einen Automaten konstruieren, der die bisherige Verarbeitung eines Wortes in einem gewissen Umfang speichern kann. Im Beispiel muss der Automat "wissen" wieviele 'a' vorkamen, wenn das erste 'b' auftritt. Dies leistet ein Kellerautomat.

Ein Kellerautomat verfügt neben der Eingabe und inneren Zuständen zusätzlich über einen Kellerspeicher. In diesem kann er das oberste Zeichen durch eine Zeichenfolge aus einem Kelleralphabet K ersetzen.
Der Kellerspeicher oder Keller erlaubt also immer nur den Zugriff auf das oberste, d.h. zuletzt abgelegte Zeichen. Er funktioniert nach dem Prinzip LIFO (last input, first output). Anfangs enthält der Keller nur das Startsymbol k0 Î K, d.h. der Keller ist leer.
Die Bearbeitung einer Eingabe stoppt, wenn das Eingabewort vollständig bearbeitet ist. Befindet sich der Automat in einem Endzustand, unabhängig vom Zustand des Kellers, so wird das Eingabewort akzeptiert.
Arbeitsweise des Kellerautomaten

Mit dem Kellerautomaten lässt sich obige Aufgabe, die Erkennung der Sprache zum Ausdruck a = anbn lösen: Zur Lösung.

Der Kellerautomat ist eine Erweiterung der endlichen Automaten, denn benutzt man den Keller nicht, so stimmt die Sprache des Kellerautomaten mit der des entsprechenden endlichen Automaten überein, wenn man dieselben Zustände verwendet und die Übergange (s,e,k0) -> (s',k0) ersetzt durch (s,e) -> s'. Umgekehrt kann man jeden endlichen Automaten durch einen Kellerautomaten ersetzen, der dieselbe Sprache erkennt.

[Index] [Zurück/Automaten 4]


Autor: Jürgen Dehmer
Letzte Änderung: