Die informationstheoretische Darstellung von Automaten

Wir stellen die allgemeine Darstellung von endlichen Automaten vor. und erklären die Begriffe Zustand, Übergang und Eingabealphabet.

Automaten setzen sich aus Zuständen und Übergängen zusammen. Ein Automat befindet sich zu jedem Zeitpunkt in genau einem Zustzand. Eine Übergangsfunktion beshreibt, mit welchem  Zeichen von einem Zustand in einen anderen gewechselt werden kann.

Betrachten wir das vorangegangene Beispiel "Parkscheinautomat": 

Diese Darstellung nennt man "Übergangsgraph" des Parkautomaten

Folgende Zustäne hat der Automat:

q1: Der Automat erwartet eine Eingabe.

q2: Der Automat hält den eingeworfenen Geldbetrag fest.

q3: Der Automat druckt den Parkschein

Weiterhin besitzt der Automat diese Übergänge:

v1: Eine Münze wird eingeworfen ⇒ Wechsel von q1 zu q2

v2: es werden weitere Münzen eingeworfen ⇒  Der Automat bleibt in q2 und bestimmt die Parkdauer.

v3: Der Schalter "Parkschein drucken" wird gedrückt ⇒ Der Automat wechselt in q3

v4: Wenn der Parkschein gedruckt ist, wechselt der Automat in q1.

Ein Übergang erfolgt immer nur dann, wenn eine erlaubte Eingabe erfolgt ist. Die Menge der erlaubten Eingaben nennen die Informatiker*innen "Eingabealphabeth".