Quelltext der Seite Kellerautomat

Ein '''Kellerautomat''' ('''KA''', auch ''PDA'' für [[Englische Sprache|englisch]] '''''p'''ush'''d'''own <!-- sic! -->'''a'''utomaton''; auch ''Stackmaschine'') ist ein [[Automat (Informatik)|Automat]] im Sinne der [[Theoretische Informatik|theoretischen Informatik]], ein Konstrukt, das verwendet wird, um gewisse Eigenschaften von [[Problem]]en und [[Algorithmus|Algorithmen]] zu [[Analyse|analysieren]] und zu [[Beweis (Mathematik)|beweisen]].

Der Kellerautomat ist ein [[endlicher Automat]], der um einen [[Stapelspeicher|Kellerspeicher]] (auch genannt Stack) erweitert wurde. Ein [[Zweikellerautomat|Kellerautomat mit zwei Kellerspeichern]] ist gleichmächtig zur [[Turingmaschine]].

== Funktionsweise ==

[[Datei:Kellerautomat.svg|mini|Kellerautomat]]
Ein Kellerautomat dient dazu, zu klären, ob eine Eingabe (d.&nbsp;h. ein [[Wort (Theoretische Informatik)|Wort]] aus null, einem oder mehreren Zeichen) zu einer bestimmten [[Formale Sprache|formalen Sprache]] (d.&nbsp;h. einer Menge von Wörtern) gehört. Dafür arbeitet der Automat das Eingabewort Schritt für Schritt von links nach rechts ab und kann dabei eine Reihe von Zuständen annehmen. Zu Anfang ist er im sogenannten Startzustand. Typischerweise wird in jedem Verarbeitungsschritt ein Zeichen aus der Eingabe gelesen. Außerdem wird in jedem Verarbeitungsschritt das oberste Zeichen vom [[Stapelspeicher|Keller]] gelesen, d.&nbsp;h. entfernt. Abhängig vom aktuellen Zustand, dem gerade gelesenen Eingabezeichen und dem gerade gelesenen Kellerzeichen geht der Automat in einen neuen Zustand über und legt anstelle des entfernten Kellerzeichens ein neues Wort auf dem Keller ab. Wenn die gesamte Eingabe gelesen wurde und der Keller leer ist, gehört die Eingabe zur vom Automaten erkannten Sprache.

Allgemein sind allerdings mehrere Abweichungen von der obigen Erklärung möglich:
* Die erkannte Sprache kann auch als die Menge der Wörter definiert werden, bei deren Abarbeitung der Kellerautomat einen sogenannten Endzustand erreicht – unabhängig davon, ob dabei der Keller geleert wird.
* Nicht in jedem Verarbeitungsschritt muss ein Zeichen aus der Eingabe gelesen werden. Wenn keins gelesen wurde, wird das gelesene Wort als [[Epsilon|<math>\varepsilon</math>]] (das [[Leeres Wort|leere Wort]]) bezeichnet.
* Für manche Kombinationen von Zustand, Eingabezeichen (oder <math>\varepsilon</math>) und Kellerzeichen kann der Kellerautomat die Wahl zwischen mehreren Übergängen (also Kombinationen von Folgezustand und Kellerwort) haben. Die Eingabe gilt in diesem Fall als erkannt, wenn der Keller geleert werden ''kann'' bzw. ein Endzustand erreicht werden ''kann''.

=== Beispiel ===

Um das Prinzip eines Kellerautomaten zu verdeutlichen, wird häufig die syntaktische Untersuchung [[Dyck-Sprache|geklammerter Ausdrücke]] herangezogen. Beispielsweise muss in einem Ausdruck einer bestimmten Sprache zu jeder öffnenden Klammer auch eine schließende Klammer existieren:

: Beispiel: { … { … } … }

Der Automat beginnt in einem Startzustand ''z0''; im Keller befindet sich ein Zeichen, welches das Ende kennzeichnet (''#''). Bei der Abarbeitung des Ausdrucks bewegt sich der Lesekopf Zeichen für Zeichen weiter. Stößt er dabei auf eine öffnende Klammer, so wird diese in den Keller geschrieben. Tritt in der weiteren Abarbeitung eine schließende Klammer auf, so wird das oberste Klammer-auf-Zeichen im Keller wieder gelöscht. Der Ausdruck ist dann erfolgreich abgearbeitet, wenn der Lesekopf das Ende des Eingabebandes erreicht hat und sich im Keller ausschließlich das Zeichen ''#'' befindet. Befände sich hingegen noch eine geöffnete Klammer nach der Ausdrucksabarbeitung im Keller, so würde dies bedeuten, dass eine schließende Klammer fehlt und ein syntaktischer Fehler vorliegt. Auch wenn das Ende des Kellers erreicht wird, bevor die Eingabe vollständig abgearbeitet wurde, liegt ein Fehler vor. In diesem Fall befinden sich zu viele schließende Klammern in der Eingabe.

== Formale Definition ==

Ein ''nichtdeterministischer'' Kellerautomat (NKA) wird definiert als ein 7-[[Tupel]] <math>M=(Z,\Sigma,\Gamma,\delta,z_0,\#,F)</math>, wobei

* <math>Z\,</math> eine endliche [[Menge (Mathematik)|Menge]] von Zuständen,
* <math>\Sigma\,</math> ein Eingabe[[Alphabet (Informatik)|alphabet]],
* <math>\Gamma\,</math> das Kelleralphabet,
* <math>\delta\,</math> die Zustandsübergangsfunktion, <math>\delta \colon Z \times (\Sigma \cup \{ \varepsilon \} ) \times \Gamma \rightarrow \mathcal P(Z \times \Gamma^{*})</math>, die nur auf ''endliche'' Teilmengen von <math>Z \times \Gamma^*</math> abbildet,
* <math>z_0\in Z</math> der Startzustand,
* <math>\# \in \Gamma</math> das Anfangssymbol im Keller und
* <math>F \subseteq Z</math> eine [[Menge (Mathematik)|Menge]] von Endzuständen

ist.

Dabei bezeichnet <math>\varepsilon</math> das [[Leeres Wort|leere Wort]] und <math>\Gamma^{*}</math> die Menge der Wörter des Alphabets <math>\Gamma</math>.

Manchmal findet man auch Kellerautomaten als 6-[[Tupel]] <math>M=(Z,\Sigma,\Gamma,\delta,z_0,\#)</math>, in diesem Fall gibt es keine Endzustände, und der Kellerautomat akzeptiert ein Wort, falls nach der Abarbeitung des Wortes der Keller leer ist.

Wenn die Übergangsfunktion die Eigenschaft <math>\forall z \in Z, \forall a \in \Sigma, \forall g \in \Gamma, \left|\delta(z,a,g)\right| + \left|\delta(z,\varepsilon,g)\right|\leq 1</math> erfüllt, spricht man von einem ''deterministischen'' Kellerautomaten. Zu einer festen Eingabe gibt es dann höchstens eine Zustandsübergangsabfolge, Mehrdeutigkeiten können also nicht auftreten.

=== Anmerkungen ===

* Für einen [[Nichtdeterminismus|nichtdeterministischen]] Kellerautomaten ist es möglich, in der Definition auf die Menge der Endzustände zu verzichten. Stattdessen definiert man, dass der nichtdeterministische Kellerautomat seine Eingabe akzeptiert, wenn es einen Berechnungspfad gibt, bei dem nach dem Einlesen der Eingabe der Keller das leere Wort enthält. Die beiden Definitionen sind hinsichtlich der akzeptierten Sprachen äquivalent. Für einen deterministischen Kellerautomaten ist diese Aussage im Allgemeinen jedoch falsch. Der deterministische Kellerautomat, der über Endzustände akzeptiert, ist mächtiger.
* Das heißt, dass ein deterministischer Kellerautomat terminieren kann, sobald ein Endzustand erreicht wurde, aber nicht sofort terminieren muss. Dabei spielt der Keller keine Rolle. Er akzeptiert ein Wort, wenn er terminiert und das Eingabewort leer ist. Ist es nicht leer und es sind keine Regeln mehr anwendbar, wurde es nicht akzeptiert.
* Für einen solchen bei leerem Keller akzeptierenden nichtdeterministischen Kellerautomaten ist es möglich, einen äquivalenten Kellerautomaten mit einem einzigen Zustand zu konstruieren, indem die Zustände des alten Kellerautomaten vollständig im Keller des neuen Kellerautomaten simuliert werden. In der Definition eines nichtdeterministischen Kellerautomaten kann also neben der Menge der Endzustände auch zusätzlich auf den Startzustand und die Zustandsmenge verzichtet werden.
* Es kann in der Definition eines nichtdeterministischen Kellerautomaten auf <math>\varepsilon</math>-Übergänge verzichtet werden. Die Zustandsübergangsfunktion ist dann ein Element aus <math>(Z \times \Sigma \times \Gamma) \to \mathcal P (Z \times \Gamma^*)</math>. Mit Hilfe der [[Greibach-Normalform]] zeigt man, dass zu jedem nichtdeterministischen Kellerautomaten ein äquivalenter nichtdeterministischer Kellerautomat ohne <math>\varepsilon</math>-Übergänge existiert.

=== Akzeptierte Sprache ===
Die Menge der ''Konfigurationen'' eines Kellerautomaten ist <math>K=Z\times\Sigma^*\times\Gamma^*</math>. Ein Element <math>(z,\alpha,\gamma)\in K</math> dieser Menge besteht aus
* dem aktuellen Zustand <math>z</math>,
* dem noch zu lesenden Wort <math>\alpha</math> sowie
* dem Kellerinhalt <math>\gamma</math>.

Auf <math>K</math> wird eine Relation <math>{\rightsquigarrow}\subseteq K\times K</math> definiert, über die im Anschluss festgelegt wird, welche Worte akzeptiert werden. Es ist
: <math>
\begin{align}{\rightsquigarrow} := &\ 
\{((z,a\alpha,g\gamma),(z',\alpha,\gamma'\gamma)) \mid
z\in Z, a\in\Sigma, \alpha\in\Sigma^*, g\in\Gamma, \gamma,\gamma'\in\Gamma^*, (z',\gamma')\in\delta(z,a,g)\} \\
\cup &\ \{((z,\alpha,g\gamma),(z',\alpha,\gamma'\gamma)) \mid
z\in Z, \alpha\in\Sigma^*, g\in\Gamma, \gamma,\gamma'\in\Gamma^*, (z',\gamma')\in\delta(z,\varepsilon,g)\}.
\end{align}</math>

Für Automaten, deren Endzustandsmengen über die Akzeptanz entscheiden sollen, heißt es dann:
: <math>\alpha\in\Sigma^*</math> wird von <math>M</math> genau dann akzeptiert, wenn es ein <math>f\in F</math> sowie ein <math>\gamma\in\Gamma^*</math> gibt, sodass <math>(z_0, \alpha, \#) \rightsquigarrow^* (f, \varepsilon, \gamma)</math>.

Für Automaten hingegen, bei denen die Akzeptanz davon abhängt, ob der Keller leer ist, lautet die Formulierung:
: <math>\alpha\in\Sigma^*</math> wird von <math>M</math> genau dann akzeptiert, wenn es ein <math>z\in Z</math> gibt, sodass <math>(z_0,\alpha,\#) \rightsquigarrow^* (z, \varepsilon, \varepsilon)</math> oder <math>(z_0,\alpha,\#) \rightsquigarrow^* (z, \varepsilon, \#)</math>.

Dabei ist <math>\rightsquigarrow^*</math> die [[Reflexive Relation|reflexive]] und [[Transitive Relation|transitive]] [[Hüllenoperator|Hülle]] von <math>\rightsquigarrow</math>.

=== Beispiele ===

Der folgende Kellerautomat ''M'' ist deterministisch und erkennt die [[Kontextfreie Sprache|kontextfreie]] Sprache <math>L = \{a^n\,b^n\,|\,n > 0\}</math>:

<math>M=(Z,\Sigma,\Gamma,\delta,z_0,\#,F)</math>
* <math>Z = \left\{ {z_0}, {z_1}, {z_2} \right\}</math>
* <math>\Sigma = \left\{ a, b \right\}</math>
* <math>\Gamma = \left\{ \#, a \right\}</math>
* <math>F = \left\{ {z_2} \right\}</math>

{| class="wikitable"
|+ Definition für δ
|-
! colspan="3" class="hintergrundfarbe6"| Parameter
! colspan="2" class="hintergrundfarbe8"| Funktionswert
|-
|class="hintergrundfarbe6" | Zustand
|class="hintergrundfarbe6" | Eingabe
|class="hintergrundfarbe6" | Keller
|class="hintergrundfarbe8" | Zustand
|class="hintergrundfarbe8" | Keller
|-
| z<sub>0</sub> || a || # || z<sub>0</sub> || a# || (1)
|-
| z<sub>0</sub> || a || a || z<sub>0</sub> || aa || (2)
|-
| z<sub>0</sub> || b || a || z<sub>1</sub> || ε  || (3)
|-
| z<sub>1</sub> || b || a || z<sub>1</sub> || ε  || (4)
|-
| z<sub>1</sub> || ε || # || z<sub>2</sub> || ε  || (5)
|}
[[Datei:Pushdown Automaton Example.svg|mini|Beispiel-Kellerautomat]]
* (1), (2) Im Zustand z<sub>0</sub> werden die führenden a-Zeichen der Eingabe gelesen und im Keller gespeichert.
* (3) Bei Eingabe ''b'' und einem ''a'' als oberstes Kellerelement erfolgt ein Zustandswechsel von z<sub>0</sub> zu z<sub>1</sub>. Abgleich im Keller erfolgt. (Abgleich bedeutet „Löschen“ des obersten Stack-Elementes bzw. Stack „pop“)
* (4) Alle weiteren b-Zeichen werden gelesen, sofern noch genügend a-Zeichen im Keller gespeichert sind. Der Keller wird abgeglichen.
* (5) Wenn sich nur noch das Anfangssymbol <math>\#\,</math> im Keller befindet und keine Eingabe erfolgt, geht der Kellerautomat in den Endzustand z<sub>2</sub> über und akzeptiert damit die Eingabe.

Erhält der Kellerautomat beispielsweise die Eingabe ''aabb'', so durchläuft er folgende Konfigurationen:

(die hochgestellte Nummer am Pfeil kennzeichnet die benutzte Zustandsübergangsfunktion)

(z<sub>0</sub>, aabb, #) ⇝<sup>(1)</sup> (z<sub>0</sub>, abb, a#) ⇝<sup>(2)</sup> (z<sub>0</sub>, bb, aa#) ⇝<sup>(3)</sup> (z<sub>1</sub>, b, a#) ⇝<sup>(4)</sup> (z<sub>1</sub>, ε, #) ⇝<sup>(5)</sup> (z<sub>2</sub>, ε, ε)

Dieser Kellerautomat M kann grundsätzlich, wenn er begonnen hat, den Keller zu lesen, nicht wieder schreiben. Daher ist die erkannte Sprache insbesondere auch eine [[lineare Sprache]].

Gegeben ist die [[kontextfreie Sprache]] mit der [[Kontextfreie Grammatik|kontextfreien Grammatik]] <math>G=(V,T,P,S)</math> mit <math>T = \{ [, ] \}</math>, <math>N = \{S\}</math> und den [[Produktionsregel]]n<ref>University of Delaware: [https://www.eecis.udel.edu/~isafro/fa21/part5-pda.pdf Pushdown Automata]</ref>

: <math>\begin{align}
S & \rightarrow [S] \\
S & \rightarrow SS \\
S & \rightarrow \varepsilon \\
\end{align}
</math>

Diese Sprache definiert genau die [[Zeichenkette]]n aus linken und rechten [[Eckige Klammer|eckigen Klammern]], die die gleiche Anzahl von linken und rechten Klammern enthält und kein Präfix mit mehr rechten als linken Klammern enthält.

Der folgende Kellerautomat ''<math>M</math>'' ist deterministisch und erkennt diese [[kontextfreie Sprache]]:

<math>M=(Z,\Sigma,\Gamma,\delta,z_0,\#,F)</math>
* <math>Z = \left\{ {z_0}, {z_1}, {z_2} \right\}</math>
* <math>\Sigma = \left\{ [, ] \right\}</math>
* <math>\Gamma = \left\{ \#, [ \right\}</math>
* <math>F = \left\{ {z_2} \right\}</math>

== Kellerautomaten und formale Sprachen ==

Ein (Keller-)Automat liest eine aus einzelnen Zeichen bestehende Eingabe und akzeptiert (oder erkennt) diese – oder auch nicht. Die Menge der akzeptierten Eingaben bildet die durch den Automaten definierte [[Formale Sprache|Sprache]].

Der [[Nichtdeterminismus|nichtdeterministische]] Kellerautomat erkennt genau die [[Kontextfreie Sprache|kontextfreien Sprachen]] (Typ&nbsp;2, vgl. [[Chomsky-Hierarchie]]). Er ist damit mächtiger als [[Endlicher Automat|endliche Automaten]], welche genau die [[Reguläre Sprache|regulären Sprachen]] (Typ&nbsp;3) erkennen, aber weniger mächtig als [[Turingmaschine]]n, welche genau die [[Rekursiv aufzählbare Sprache|rekursiv aufzählbaren Sprachen]] (Typ&nbsp;0) erkennen. Ein [[Determinismus (Algorithmus)|deterministischer]] Kellerautomat (DPDA) erkennt die [[Deterministisch kontextfreie Sprache|deterministisch-kontextfreien Sprachen]], also nur eine echte Teilmenge der kontextfreien Sprachen.

Die Bedeutung des Kellerautomaten ergibt sich also daraus, dass sich Erkenntnisse über diesen (beispielsweise Äquivalenz mit anderen Automaten) auf die kontextfreien Sprachen übertragen lassen (und umgekehrt).

== Praktische Implementierung eines Kellerautomaten ==

Als praktisches Anwendungsbeispiel eines Kellerautomaten sei folgender Parser (implementiert in [[C (Programmiersprache)|C]]) gegeben, welcher eine Sprache, die aus Klammerpaaren besteht, parst und auf Richtigkeit prüft. Der Ausdruck ''()((()()))'' würde beispielsweise akzeptiert werden, falsch hingegen wäre ''(()()))'', da hier eine schließende Klammer zu viel gegeben ist.

<syntaxhighlight lang="c">
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define POP -1
#define ACCEPT -2
#define ERROR -3

#define ALPHABET 3 /* Größe des Eingabealphabets */

#define MAX_LEN 80
/*
 Ein einfacher Kellerautomat ("pushdown automaton")

 Symbol   | (       | )      | \0
 ---------+---------+--------+-----------
 State 0  | PUSH 1  | ERROR  | ACCEPT
 State 1  | PUSH 1  | POP    | ERROR
*/

int states[2][ALPHABET*2] =
{
   {
      '(', 1 /* PUSH 1 */,
      ')', ERROR,
      '\0', ACCEPT
   },
   {
      '(', 1 /* PUSH 1 */,
      ')', POP,
      '\0', ERROR
   }
};


int main( int argc, char** argv )
{
   int stack[100] = { 0 };
   int i  = 0;
   int action  = 0;
   int* tos  = stack;
   char s  [MAX_LEN+1];
   char* p  = s;

   /* Eingabe-Zeichenkette */
   printf("Bitte Ausdruck eingeben: ");
   fgets(s, sizeof(s), stdin);
   s[strlen(s)-1]='\0'; /* Zeilenvorschub (NL) von fgets() durch binäre Null ersetzen */


   /* Startzustand auf Stack ("push") */
   *(tos++) = 0;

   /* Ausführungsschleife */
   do
   {
      /* Aktion auf Basis des Eingabesymbols ermitteln */
      action = ERROR;
      for( i = 0; i < ALPHABET; ++i )
      {
         if( states[*(tos-1)][i*2] == *p )
         {
            action = states[*(tos-1)][i*2+1];
            break;
         }
      }

      /* Ausführen der Aktionen */
      if( action == ERROR )
      {
         printf("Unerwartetes Zeichen an Position %d\n", p-s);
         break;
      }
      else if( action == ACCEPT )
         printf("Ausdruck akzeptiert!\n");
      else if( action == POP )
         --tos;
      else
         *(tos++) = action;

      /* Eingabe erweitern... */
      ++p;
   }
   while( action != ACCEPT );

   return 0;
}
</syntaxhighlight>

== Anwendungen in Technik und Wissenschaft ==

Die Gleitkommaeinheit (engl. ''Floating Point Unit'', FPU) der Intel-32-Bit x86-Architektur ist ursprünglich als Kellerautomat (engl. ''Stack Machine'') realisiert. Ihr Kellerspeicher besitzt eine Tiefe von 8 Speicherplätzen (für jeweils einen 80-Bit-Gleitkommawert). Angesichts der Einschränkungen durch das Kellermodell ist tendenziell jedoch erkennbar, dass künftig auch im PC –&nbsp;wie in anderen Rechnerarchitekturen üblich&nbsp;– vorwiegend Verarbeitungseinheiten mit direkt adressierbaren Registern verwendet werden ([[Single Instruction Multiple Data|SIMD]]-Erweiterung).

[[Compiler]] oder [[Interpreter]] von Programmiersprachen können mit Hilfe von Kellerautomaten entwickelt werden. Der Kellerautomat dient dabei der Syntaxanalyse, das heißt, er überprüft die syntaktische Korrektheit einer [[Token (Compilerbau)|Tokenfolge]].

== Siehe auch ==

* [[Registermaschine]]
* [[umgekehrte polnische Notation]] (Postfix-Notation)
* [[Akzeptor (Informatik)|Akzeptor]]
* [[Compiler]]
* [[Parser]]

== Weblinks ==
{{Wiktionary}}
<!--* www.die.informatik.uni-siegen.de/DIE_BIB/Lehre/ele/Materialien/WiSe%202002-03/Kellerautomat/WiSe%202002-03/Kellerautomat/index.htm Interaktive Veranschaulichung der Funktionsweise eines Kellerautomaten bei der Universität Siegen *** 2010-11-30: Material aus dem WS 2002/03 nicht mehr verfügbar -->

== Einzelnachweise ==
<references/>

[[Kategorie:Automatentheorie]]
[[Kategorie:Rekursion]]