Kellerautomat

nur relevant für den Leistungskurs!

Ein Kellerautomat ist ein Deterministischer Endlicher Automat (DEA), der um einen Speicher (genannt Keller) in Form eines Stack erweitert wurde. In dem Keller kann der Kellerautomat Zeichen, die im sogenannten Kelleralphabet definiert sind, speichern und sie später nach dem Last-In-First-Out-Prinzip wieder abrufen.

Fachbegriffe

Alphabet, Zeichen, Kelleralphabet, Kellerzeichen, Zustand, Anfangszustand, Endzustände, Übergang

Zweck des Kellerautomaten

Deterministische Endliche Automaten können nur sehr begrenzte Sprachen überprüfen, vor allem deswegen, weil sie nicht "zählen" können. Deswegen ist z.B. die Sprache L = {aⁿbⁿ} mit einem DEA nicht darstellbar.

Ein Kellerautomat kann diese Sprache überprüfen!

Beispiel

Die Darstellung rechts entspricht der "SIBI-internen" Schreibweise.
So darf man in Klausuren schreiben!
Die Standard-Schreibweise (s.u.) muss man aber mindestens lesen können.

Kellerautomat für die Sprache L = {aⁿbⁿ}.

Der folgende Kellerautomat überprüft die Sprache L = {aⁿbⁿ}.

Erläuterung:

• Q = {q₀, q₁, q₂}
• A = {a, b}
• K = {#, A}
  dabei ist # das Anfangssymbol im Keller (d.h. es steht für einen leeren Keller)
• d: siehe rechts
• Startzustand: q₀
• F = {q₂} ist die Menge der Endzustände

Beispiel in Standard-Schreibweise

Die Standard-Schreibweise wird im Zentralabitur, aber auch von Wikipedia genutzt.

Die Standard-Schreibweise muss man mindestens lesen können.
Zum Schreiben ist auch die SIBI-interne Schreibweise (s.o.) möglich.

Standardschreibweise für die Sprache L = {aⁿbⁿ}.

Der Zustandsübergangsgraph rechts zeigt die Standard-Schreibweise für einen Kellerautomaten, der die Sprache Sprache L = {aⁿbⁿ} überprüft.

Erläuterung:

• In der Klammer steht zuerst das aktuelle Kellerzeichen (d.h. das oberste Zeichen auf dem Keller-Stapel) und dann der Buchstabe des Wortes, der gerade bearbeitet wird.
• Nach dem Doppelpunkt steht der Zustand des Kellers nach Abarbeitung.
  Dabei bedeutet...
  • € : das oberste Zeichen im Keller wurde gelöscht (d.h. pop)
  • ein Buchstabe : der Keller hat sich nicht verändert (d.h. nop).
  • zwei Buchstaben : es wurde ein Kellerzeichen oben in den Keller reingeschichtet.
    Der erste der beiden Buchstaben ist das neue Kellerzeichen,
    der zweite Buchstabe ist das bisherige oberste Kellerzeichen.

Formale Definition des Kellerautomaten

Der Kellerautomat ist ein 7-Tupel (Q, A, K, d, q₀, #, F)

Dabei ist:

• Q: endliche Menge von Zuständen = {q₀, ..., q_n}
• A: Das endliche Eingabealphabet
• K: das endliche Kelleralphabet
• d: die Übergangsfunktion:
  Sie berechnet aus einem Zustand, einem Eingabezeichen und einem Kellerzeichen
  einen Nachfolgezustand und eine Kelleroperation
• q₀ist der Startzustand.
• # ist das Anfangssymbol im Keller
• F ist die Menge der akzeptierenden Endzustände.

Deterministischer und Nicht-Deterministischer Kellerautomat

Der nicht-deterministische Kellerautomat ist mächtiger als der deterministische Kellerautomat!
D.h. es gibt Sprachen, die von einem Nicht-Deterministischen Kellerautomaten geprüft werden können, nicht aber von einem Deterministischen Kellerautomaten.

Beispiel

Die von der kontextfreien Grammatik erzeugte Sprache

L = { 0S0 | 1S1 | ε }

kann zwar von einem nicht-deterministischen Kellerautomaten erkannt werden,
aber nicht von einem deterministischen Kellerautomaten.

Warum das so ist?! Das geht über das Geschehen auch im Informatik-LK hinaus.
Damit kann/muss man sich im Informatik-Studium (Vorlesung: Theoretische Informatik) auseinandersetzen...

Zusammenhang zur kontextfreien Grammatik

• Jede von einer kontextfreien Grammatik erzeugte Sprache lässt sich durch einen nicht-deterministischen Kellerautomat überprüfen.
• Zu jeder von einem nicht-deterministischen Kellerautomaten erkannten Sprache gibt es eine kontextfreie Grammatik.

Die Frage nach dem "Warum?" geht auch über den Informatik-LK hinaus und bleibt hier unbeantwortet.
Irgendetwas muss ja auch für das Studium noch übrig bleiben...

Parser für einen Kellerautomaten

Die folgende Programmierung realisiert den Übergangsgraphen (s.o.) in Java:

   public boolean parse(String pWort){
       // ein € anhaengen
       // erleichtert die Ueberpruefung des Endes!
       pWort += '€';
       Stack<Character> keller = new StackWithViewer<Character>();
       keller.push('#');
       int zustand = 0;
       for(int i=0; i<pWort.length(); i++){
           char zeichen = pWort.charAt(i);
           char kellerzeichen = keller.top();
           if(zustand == 0){
                   if(zeichen=='a' && kellerzeichen == '#'){
                       zustand = 0;
                       keller.push('A');
                   }
                   else if(zeichen=='a' && kellerzeichen == 'A'){
                       zustand = 0;
                       keller.push('A');
                   }
                   else if(zeichen =='b' && kellerzeichen == 'A'){
                       zustand = 1;
                       keller.pop();
                   }
                   else{
                       return false;
                   }
                   continue;                   
                   // end case 0
            else if(zustand == 1){
                   if(zeichen=='b' && kellerzeichen == 'A'){
                       zustand = 1;
                       keller.pop();
                   }
                   else if(zeichen=='€' && kellerzeichen == '#'){
                       zustand = 2;
                   }
                   else{
                       return false;
                   }
                   continue;
                   // end case 1
           }
           else{
                   // andere Zustaende, d.h. Zustand 2
                   System.err.println("Im Zustand 2 darf es kein Zeichen mehr geben!!");
                   return false;
           }
       }    // end for
    
       // Das Wort ist abgearbeitet!
       // Ueberpruefen, ob Endzustand erreicht
       return (zustand == 2);
   }