Logo des digitalen Schulbuchs inf-schule.de. Schriftzug in Zustandsübergangsdiagramm eines endlichen Automaten.

Fachkonzept - Endlicher Automat

Grundidee

Die Grundidee soll ausgehend von einem Automaten der Lebenswelt beschrieben werden.

Ein Kunstautomat wird hier als Verarbeitungseinheit modelliert, die aus Eingaben - in Abhängigkeit des aktuellen Zustands - Ausgaben erzeugt und gegebenenfalls in einen neuen Zustand wechselt.

Automat als Verarbeitungseinheit

Wesentliches Merkmal dieser Verarbeitungseinheit ist, dass nur endlich viele Verarbeitungszustände eingenommen werden können und dass nur eine endliche Zahl von Eingaben verarbeitet werden. Infolgedessen sind auch nur endlich viele Ausgaben möglich.

Zustände:

z0: 0 Euro eingezahlt
z1: 1 Euro eingezahlt
z2: 2 Euro eingezahlt
z3: 3 Euro eingezahlt

Eingaben (Ereignisse):

e1: 1-Euro-Münze einwerfen
e2: 2-Euro-Münze einwerfen
eKorrektur: Korrektur-Taste drücken
eWare: Ware-Taste drücken

Ausgaben (Aktionen):

aNichts: nichts auswerfen
a1: 1 Euro auswerfen
a2: 2 Euro auswerfen
a3: 3 Euro auswerfen
aWare: Ware auswerfen

Die Verarbeitungslogik dieser Verarbeitungseinheit kann mit Hilfe eines Zustandsdiagramms festgelegt werden.

Zustandsdiagramm

Dieses Zustandsdiagramm legt den Anfangszustand und die Zuständsübergänge bei der Verarbeitung von Eingaben fest.

Die Zustandsübergänge können auch mit Hilfe einer Tabelle beschrieben werden:

aktueller Zustand Eingabe Ausgabe neuer Zustand
z0 e1 aNichts z1
z0 e2 aNichts z2
z0 eKorrektur aNichts z0
z0 eWare aNichts z0
z1 e1 aNichts z2
z1 e2 aNichts z3
z1 eKorrektur a1 z0
z1 eWare aNichts z1
... ... ... ...

Präzisierung

Verarbeitungseinheiten, die in Abhängigkeit des aktuellen Zustands aus Eingaben Ausgaben erzeugen und gegebenenfalls in einen neuen Zustand wechseln, kommen häufig vor und sollen daher weiter präzisiert werden.

Ein endlicher Automat (kurz: EA) ist eine Verarbeitungseinheit, die durch folgende Bestandteile festgelegt wird:

  • eine nichtleere, endliche Menge Z von Zuständen
  • eine nichtleere, endliche Menge E von Eingabesymbolen
  • eine nichtleere, endliche Menge A von Ausgabesymbolen
  • eine Überführungsfunktion f: Z x E -> Z, die jedem Paar aus aktuellem Zustand und Eingabe einen Folgezustand zuordnet
  • eine Ausgabefunktion g: Z x E -> A, die jedem Paar aus aktuellem Zustand und Eingabe eine Ausgabe zuordnet
  • ein ausgezeichnetes Element z0 ∈ Z, der sogenannte Anfangszustand

Für den oben gezeigten Getränkeautomaten erhält man folgende Komponenten.

X

Fehler melden

X

Suche