Kellerautomat: Unterschied zwischen den Versionen

Aus SibiWiki
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=
Der folgende Kellerautomat überprüft die Sprache L = {a<sup>n</sup>b<sup>n</sup>}
[[File:Kellerautomat.png|thumb|Kellerautomat für die Sprache L = {a<sup>n</sup>b<sup>n</sup>}. |351px]]


<font color='red'>TODO: Bild einfügen</font>
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

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

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.