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 Kellerzeichen 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.

Zusammenhang zur kontextfreien Grammatik

• Der deterministische Kellerautomat erkennt genau die deterministisch-kontextfreien Sprachen.
• Der nichtdeterministische Kellerautomat erkennt genau die kontextfreien Sprachen, d.h. Sprachen, die von einer kontextfreien Grammatik erzeugt werden.

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);
   }