Kellerautomat: Unterschied zwischen den Versionen
Zur Navigation springen
Zur Suche springen
(Die Seite wurde neu angelegt: „Kategorie:endliche Automaten Kategorie:Informatik-Q2 Kategorie:Informatik-Abitur Kategorie:Informatik Ein Kellerautomat ist ein Deterministi…“) |
|||
| Zeile 15: | Zeile 15: | ||
=Beispiel= | =Beispiel= | ||
[[File:Kellerautomat.png|thumb|Kellerautomat für die Sprache L = {a<sup>n</sup>b<sup>n</sup>}. |351px]] | |||
< | Der folgende Kellerautomat überprüft die Sprache L = {a<sup>n</sup>b<sup>n</sup>}. | ||
Erläuterung: | |||
* Q = {q<sub>0</sub>, q<sub>1</sub>, q<sub>2</sub>} | |||
* A = {a, b} | |||
* K = {#, A} <br>dabei ist # das Anfangssymbol im Keller (d.h. es steht für einen leeren Keller) | |||
* d: '''siehe rechts''' | |||
* Startzustand: q<sub>0</sub> | |||
* F = {q<sub>2</sub>} ist die Menge der Endzustände | |||
=Formale Definition des Kellerautomaten= | =Formale Definition des Kellerautomaten= | ||
Version vom 22. November 2017, 17:58 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.