HSG

Aktuelle Seite: HSG/Fächer/Informatik/Material

Definition - aus Informatik heute, Band 2, S.105

Die Erweiterung des Akzeptors zum Kellerautomaten führt zu folgenden Ergänzungen:
  1. Kellerautomaten besitzen ein Kelleralphabet, in dem alle Zeichen enthalten sind, die im Keller gespeichert werden können. Das Kellerstartzeichen gehört zum Kelleralphabet. Es ist zu Beginn im Keller gespeichert.
  2. Die Übergänge zwischen den inneren Zuständen hängen nicht nur von den Eingaben, sondern auch vom obersten Kellerzeichen ab.
  3. Bei jedem Übergang wird auch eine Kelleroperation ausgeführt.
Leider enthält obige Definition keine präzise Aussage, wann ein Wort akzeptiert wird. In der Literatur werden hierfür zwei Möglichkeiten angegeben:
  1. Genau die Wörter, nach deren Abarbeitung der Keller leer ist, werden akzeptiert.
  2. Genau die Wörter, nach deren Abarbeitung der Automat in einem Endzustand ist, werden akzeptiert.
Man kann zeigen, dass beide Möglichkeiten äquivalent sind.
JFlap verwendet die zweite Möglichkeit. Trotzdem wollen wir uns bemühen, auch den Keller beim Akzeptieren leer zu haben.
Man beachte, dass Kellerautomaten häufig nicht-deterministisch sind.