Schema eines KA
CD-Stapel als Keller: Mit einer Hand kann ich CDs oben einfach drauflegen oder wegnehmen.
Sichtbar sind nur die Informationen zur obersten CD.
"Last in - first out"
|
Kellerautomaten besitzen einen Lesekopf und eine endliche Zustandskontrolle.
Mit dem Lesekopf wird jeweils ein Symbol der Eingabe erkannt.
Die Eingabe wird Symbol für Symbol einmal gelesen (in typischer Leserichtung) und dabei verarbeitet.
Ein Zustandswechsel kann auch erfolgen, ohne dass ein Symbol der Eingabe verarbeitet wird ( -move, spontaner Übergang)
Zur Speicherung ihrer Zwischenergebnisse nutzen sie einen "Keller" (stack).
Das ist ein zellenartig aufgebautes Speichermedium, wobei die einzelnen Zellen sowohl gelesen als auch beschrieben werden können.
Allerdings ist der Zugang zu den Zellen sehr beschränkt: Sichtbar ist immer nur die oberste Zelle.
Will der Automat eine Information im Keller speichern, so legt er sie in einer neuen Zelle an oberster Stelle ab.
Die bisherigen Kellerzellen verstecken sich unter dieser neuen Zelle. Dieser Vorgang wird als push bezeichnet.
Die Information einer Zelle ist erst wieder sichtbar, wenn die Zelle an oberster Stelle des Kellers liegt.
Das Entfernen der Information einer obersten Zelle nennt man pop.
Der Übergang von einer Konfiguration zur nächsten wird durch das aktuelle Symbol der Eingabe,
den aktuellen Zustand und den Inhalt der obersten Kellerzelle bestimmt und kann folgende Aktionen umfassen:
- Änderung des Zustands
- Verschieben des Lesekopfes
- Entfernen der obersten Kellerzelle - pop
- Hinzufügen von Informationen zum Keller - push
|
Formale Darstellung eines KA