Kellerautomat: Unterschied zwischen den Versionen
Zeile 41: | Zeile 41: | ||
=Zusammenhang zu formalen Sprachen= | =Zusammenhang zu formalen Sprachen= | ||
* Der deterministische Kellerautomat erkennt genau die deterministisch-kontextfreien Sprachen. | * Der deterministische Kellerautomat erkennt genau die deterministisch-kontextfreien Sprachen. | ||
* Der nichtdeterministische Kellerautomat erkennt genau die [[ | * Der nichtdeterministische Kellerautomat erkennt genau die kontextfreien Sprachen, d.h. Sprachen, die von einer [[Kontexfreie Grammatik|kontextfreien Grammatik]] erzeugt werden. | ||
=Programmierung eines Kellerautomaten= | =Programmierung eines Kellerautomaten= |
Version vom 24. November 2017, 19:36 Uhr
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.
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 darstellen!
Beispiel
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
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.
Zusammenhang zu formalen Sprachen
- 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.
Programmierung eines 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(char zeichen:pWort.toCharArray()){
char kellerzeichen = keller.top();
switch(zustand){
case 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
case 1:
if(zeichen=='b' && kellerzeichen == 'A'){
zustand = 1;
keller.pop();
}
else if(zeichen=='€' && kellerzeichen == '#'){
zustand = 2;
}
else{
return false;
}
continue;
// end case 1
} // end switch(zustand)
} // end for
// Das Wort ist abgearbeitet!
// Ueberpruefen, ob Endzustand erreicht
return (zustand == 2);
}