Endliche Automaten (1)

Wir wollen einen idealisierten Zigarettenautomaten simulieren, der aus einem unerschöpflichen Vorrat einer einzigen Sorte nach Einwurf des passenden Geldbetrags und Drücken der Ausgabetaste eine Schachtel auswirft. Der Preis soll DM 5 betragen; der Automat akzeptiert Geldstücke zu DM 1, DM 2 und DM 5 sowie die Taste A. Was bei Überzahlungen geschehen soll (abweisen, vereinnahmen, oder gar wechseln), und ob es eine Rückgabetaste geben soll, lassen wir vorerst offen; die Erweiterung ist leicht, macht aber unsere Beschreibung komplizierter.

Den inneren  Zustand des Automaten beschreiben wir durch ein Element aus einer endlichen Zustandsmenge Q = {Z0 .. Z5}; jeder Zustand bedeutet den bislang gespeicherten Geldbetrag. Z0 ist der Startzustand, Z5 ein Endzustand.

Die Wirkungsweise des Automaten können wir graphisch veranschaulichen durch ein Übergangsdiagramm; die Übergänge zwischen den Zuständen sind jeweils durch die aktuelle Eingabe bestimmt.

Bei größeren Zustandszahlen ist eine Übergangstafel übersichtlicher. Sie kann als Wertetabelle einer Funktion vom Typ [QE]Q mit zwei Argumenten gelesen werden, wobei E = {'1','2','5','A'} die Menge der zulässigen Eingaben ist, oder auch als zweidimensionale Matrix vom Typ ARRAY [Q,E] OF Q. Die leeren Felder geben an, in welchen Situationen wir das Verhalten bisher noch nicht festgelegt haben.

1 2 5 A
Z0 Z1 Z2 Z5  
Z1 Z2 Z3    
Z2 Z3 Z4    
Z3 Z4 Z5    
Z4 Z5      
Z5       Z0
Mit diesen Angaben den Automaten per Programm zu simulieren, sei den Lesern als Übungsaufgabe überlassen, ebenso die Erweiterung der Beschreibung um die Ausgabe eines Wortes über einem geeigneten Ausgabealphabet bei jedem Übergang.

zurück | Inhalt | Index | vor | Vorlesung
Klaus Lagally, 22. Februar 2000, 19:36