Kellerautomat: Unterschied zwischen den Versionen

Aus SibiWiki
Zur Navigation springen Zur Suche springen
 
(9 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 3: Zeile 3:
[[Kategorie:Informatik-Abitur]]
[[Kategorie:Informatik-Abitur]]
[[Kategorie:Informatik]]
[[Kategorie:Informatik]]
<font color='red'>'''nur relevant für den Leistungskurs!'''</font>


Ein Kellerautomat ist ein [[Deterministischer Endlicher Automat]] (DEA), der um einen Speicher (genannt '''Keller''') in Form eines [[Stack]] erweitert wurde.
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.


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=
=Zweck des Kellerautomaten=
Deterministische Endliche Automaten können nur sehr begrenzte Sprachen überprüfen, vor allem deswegen, weil sie nicht "zählen" können.
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<sup>n</sup>b<sup>n</sup>} mit einem DEA nicht darstellbar.
Deswegen ist z.B. die Sprache L = {a<sup>n</sup>b<sup>n</sup>} mit einem DEA nicht darstellbar.
Zeile 15: Zeile 20:


=Beispiel=
=Beispiel=
'''<font color='red'>Die Darstellung rechts entspricht der "SIBI-internen" Schreibweise.<br/>So darf man in Klausuren schreiben!<br/>Die Standard-Schreibweise (s.u.) muss man aber mindestens <u>lesen</u> können.</font>'''
[[File:Kellerautomat.png|thumb|Kellerautomat für die Sprache L = {a<sup>n</sup>b<sup>n</sup>}. |385px]]
[[File:Kellerautomat.png|thumb|Kellerautomat für die Sprache L = {a<sup>n</sup>b<sup>n</sup>}. |385px]]


Zeile 26: Zeile 34:
* Startzustand: q<sub>0</sub>
* Startzustand: q<sub>0</sub>
* F = {q<sub>2</sub>} ist die Menge der Endzustände
* F = {q<sub>2</sub>} ist die Menge der Endzustände
==Beispiel in Standard-Schreibweise==
Die Standard-Schreibweise wird im Zentralabitur, aber auch von Wikipedia genutzt.
'''<font color='red'>Die Standard-Schreibweise muss man mindestens <u>lesen</u> können.<br/>Zum Schreiben ist auch die SIBI-interne Schreibweise (s.o.) möglich.</font>'''
[[File:Kellerautomat-Standard-Schreibweise.png|thumb|Standardschreibweise für die Sprache L = {a<sup>n</sup>b<sup>n</sup>}. |313px]]
Der Zustandsübergangsgraph rechts zeigt die Standard-Schreibweise für einen Kellerautomaten, der die Sprache Sprache L = {a<sup>n</sup>b<sup>n</sup>} ü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. <br/>Dabei bedeutet...
** '''<code>€</code>''' :    das oberste Zeichen im Keller wurde gelöscht (d.h. <code>pop</code>)
** '''ein Buchstabe''' : der Keller hat sich nicht verändert (d.h. <code>nop</code>).
** '''zwei Buchstaben''' : es wurde ein Kellerzeichen oben in den Keller reingeschichtet.<br/>Der '''erste''' der beiden Buchstaben ist das  '''neue''' Kellerzeichen, <br/>der '''zweite''' Buchstabe ist das bisherige oberste Kellerzeichen.


=Formale Definition des Kellerautomaten=
=Formale Definition des Kellerautomaten=
Zeile 39: Zeile 63:
* F ist die Menge der akzeptierenden Endzustände.
* F ist die Menge der akzeptierenden Endzustände.


=Zusammenhang zu formalen Sprachen=
=Deterministischer und Nicht-Deterministischer Kellerautomat=
* Der deterministische Kellerautomat erkennt genau die deterministisch-kontextfreien Sprachen.
 
* Der nichtdeterministische Kellerautomat erkennt genau die kontextfreien Sprachen, d.h. Sprachen, die von einer [[Kontextfreie Grammatik|kontextfreien Grammatik]] erzeugt werden.
Der nicht-deterministische Kellerautomat ist '''mächtiger''' als der deterministische Kellerautomat!<br/>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 | &epsilon; }
 
kann zwar von einem nicht-deterministischen Kellerautomaten erkannt werden,<br/>aber nicht von einem deterministischen Kellerautomaten.
 
''Warum das so ist?! Das geht über das Geschehen auch im Informatik-LK hinaus.<br/>Damit kann/muss man sich im Informatik-Studium (Vorlesung: Theoretische Informatik) auseinandersetzen...''
 
=Zusammenhang zur kontextfreien Grammatik=
 
* Jede von einer [[Kontextfreie Grammatik|kontextfreien Grammatik]] erzeugte Sprache lässt sich durch einen <u>nicht-deterministischen</u> Kellerautomat überprüfen.
* Zu jeder von einem <u>nicht-deterministischen</u> Kellerautomaten erkannten Sprache gibt es eine [[Kontextfreie Grammatik|kontextfreie Grammatik]].
''Die Frage nach dem "Warum?" geht auch über den Informatik-LK hinaus und bleibt hier unbeantwortet. <br/>Irgendetwas muss ja auch für das Studium noch übrig bleiben...''


=Parser für einen Kellerautomaten=
=Parser für einen Kellerautomaten=
Zeile 54: Zeile 92:
         keller.push('#');
         keller.push('#');
         int zustand = 0;
         int zustand = 0;
         for(char zeichen:pWort.toCharArray()){
         for(int i=0; i<pWort.length(); i++){
            char zeichen = pWort.charAt(i);
             char kellerzeichen = keller.top();
             char kellerzeichen = keller.top();
             switch(zustand){
             '''if'''(zustand == 0){
                case 0:
                     if(zeichen=='a' && kellerzeichen == '#'){
                     if(zeichen=='a' && kellerzeichen == '#'){
                         zustand = 0;
                         zustand = 0;
Zeile 75: Zeile 113:
                     continue;                   
                     continue;                   
                     // end case 0
                     // end case 0
                case 1:
            '''else if'''(zustand == 1){
                     if(zeichen=='b' && kellerzeichen == 'A'){
                     if(zeichen=='b' && kellerzeichen == 'A'){
                         zustand = 1;
                         zustand = 1;
Zeile 88: Zeile 126:
                     continue;
                     continue;
                     // end case 1
                     // end case 1
             }   // end switch(zustand)
             }
            '''else'''{
                    // andere Zustaende, d.h. Zustand 2
                    System.err.println("Im Zustand 2 darf es kein Zeichen mehr geben!!");
                    return false;
            }
         }    // end for
         }    // end for
      
      

Aktuelle Version vom 19. Februar 2021, 10:33 Uhr

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 = {anbn} 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 = {anbn}.

Der folgende Kellerautomat überprüft die Sprache L = {anbn}.

Erläuterung:

  • Q = {q0, q1, q2}
  • A = {a, b}
  • K = {#, A}
    dabei ist # das Anfangssymbol im Keller (d.h. es steht für einen leeren Keller)
  • d: siehe rechts
  • Startzustand: q0
  • F = {q2} 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 = {anbn}.

Der Zustandsübergangsgraph rechts zeigt die Standard-Schreibweise für einen Kellerautomaten, der die Sprache Sprache L = {anbn} ü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, q0, #, F)

Dabei ist:

  • Q: endliche Menge von Zuständen = {q0, ..., qn}
  • 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
  • q0ist 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);
   }