Einführung in die Automatentheorie/2. Stunde

Zustände und Übergänge

Automaten kann man sich als eine Art "Maschine" vorstellen, die stur einem festgelegtem Schema folgt, so wie zum Beispiel eine Kaffeemaschine. Eine Kaffeemaschine kann sich in verschiedenen Zuständen befinden (warten,Kaffe kochen, Kaffee warm halten). Das festgelegte Schema sagt ihr, dass sie, wenn sie angeschaltet wird, Kaffee kochen soll. Wenn sie damit fertig ist, soll sie den Kaffee warm halten, solange, bis sie ausgeschaltet wird.
Im Allgemeinen haben alle Automaten ein solches festes vorgegebenes Schema wie eine Kaffeemaschine.

Wie wir bereits gesehen haben, setzt sich ein Automat aus Zuständen und Übergängen zusammen. Ein festgelegtes Schema gibt vor, wann ein Automat von einem Zustand in einen anderen übergeht.

Definition

Zu jedem Zeitpunkt befindet sich ein Automat in genau einem Zustand. Übergänge werden anhand einer Übergangsfunktion beschrieben. Eine Übergangsfunktion gibt an, mit welchem Zeichen von einem bestimmten Zustand in einen anderen gewechselt werden kann.

Schauen wir uns hierzu nochmal den Parkscheinautomat an.
Beschriften wir die Zustände und Übergänge ein wenig anders, sieht das ganze so aus:

Dieser Automat hat folgende Zustände:

• z₀: Der Automat wartet auf eine Eingabe. Wartezustnd

• z₁: Der Automat merkt sich, wie viel Geld eingeworfen wurde.

• z₂: Der Automat druckt das Parkticket und gibt es aus.

Außerdem hat der Automat folgende Übergänge:

• v₁: Geld wird eingeworfen.
  => Der Automat wechselt von z₀ nach z₁.

• v₂: Es wird mehr Geld eingeworfen.
  => Der Automat bleibt in z₁ und zählt die Minuten.

• v₃: Der Knopf "Parkschein ausgeben" wird gedrückt.
  => Der Automat wechselt in z₂.

• v₄: Der Parkschein wird entnommen.
  => Der Automat wechselt zurück in den Zustand z₀.

Diese Abstraktion hat den Vorteil, dass nun eine gewisse Vergleichbarkeit mit anderen Automaten geschaffen wird und so generelle Aussagen und allgemeine Betrachtungen möglich sind.

Vorlage:Arbeiten

z0	Die Kasse wartet auf die Eingabe eines Preises
z1	Ein Preis wurde eingegeben	und der Knopf "Kassieren" wurde allerdings noch nicht gedrückt
z2	Der Gesamtpreis wird angezeigt	und die Geldlade ist geöffnet
v1	Der erste Preis eines Artikels wird eingegeben
v2	Ein weiterer Preis wird eingeben
v3	Der Knopf "Kassieren" wird gedrückt
v4	Die Geldlade wird geschlossen

Besondere Zustände

Auf den Zsutand mit dem Startpfeil sind wir ja schon eingegangen, dieser Zustand heißt Startzustand.
Jeder andere Zustand hat noch einen anderen "besonderen" Zustand, einen Endzustand. der Endzustand wird im Allgemeinen durch einen doppelten Kreis gekennzeichnet. Ein Automat kann auch mehrere Endzustände haben. Dazu aber später mehr.
In unserem Beispiel ist der Startzustand gleich dem Endzustand.