Formale Definition
Ein Kellerautomat ist ein 6 Tupel, besteht also aus 6 Bestandteilen A={∑,Q,s,E,δ,Γ})
Und die Übergangsfunktion δ - hängt meist von mehreren Kritierien ab, kann zeilenweise angegeben werden.
Übergangsfunktion
Ablaufprotokoll eines Kellerautomaten
| Stack | ||||||||
| k | k | |||||||
| k | k | k | k | k | ||||
| # | # | # | # | # | # | # | # | |
| Zustand | q0 | q1 | q1 | q1 | q1 | q1 | q1 | q0 |
| Vom Übergang verbrauchtes Eingabezeichen | a | a | z | a | z | z |
Eingabe endet, q0 ist Endzustand: Wort wird akzeptiert!