Endlicher Automat

Grundidee und Funktionsweise

Ein endlicher Automat (EA), auch Zustandsmaschine oder Zustandsautomat genannt, ist ein Modell für das Verhalten eines Systems. Er besteht aus Zuständen, Zustandsübergängen und Aktionen. „Endlich“ bedeutet, dass die Menge der möglichen Zustände endlich ist. Endliche Automaten sind ein Spezialfall von Automaten und werden unter anderem für digitale Schaltungen, Steuerungen, Software sowie für Wort- und Spracherkennung verwendet.

Ein Zustand kann Informationen über die bisherige Verarbeitung enthalten: Er spiegelt wider, auf welchem Weg das System seit dem Start dorthin gelangt ist. Ein Zustandsübergang führt vom aktuellen Zustand in einen neuen Zustand, sobald die dafür festgelegten Bedingungen beziehungsweise Eingaben vorliegen. Der nächste Zustand und die Ausgabe eines EA sind somit Funktionen der Eingabe und des aktuellen Zustands.

Aktionen bilden die Ausgaben des Automaten. Man unterscheidet vier Arten:

• Eine Eingangsaktion wird beim Eintreten in einen Zustand ausgeführt, unabhängig davon, über welchen Übergang dieser erreicht wurde.
• Eine Ausgangsaktion wird beim Verlassen eines Zustands ausgeführt.
• Eine Eingabeaktion hängt vom aktuellen Zustand und von der Eingabe ab.
• Eine Übergangsaktion wird während eines bestimmten Zustandsübergangs ausgeführt.

Beim Testen eines solchen Systems sollen alle Zustände und Übergänge unter Berücksichtigung aller möglichen Eingaben überprüft werden. Einfache Abläufe lassen sich auch durch Tabellen, Matrizen oder Programmablaufpläne darstellen; endliche Automaten eignen sich jedoch auch zur Modellierung größerer und komplizierterer Szenarien.

Darstellung und Hauptklassen

Ein endlicher Automat kann als Zustandsübergangsdiagramm dargestellt werden. Dabei stehen Kreise für Zustände; im Kreis befindet sich jeweils der Zustandsname. Pfeile zwischen den Kreisen stellen Transitionen, also Zustandsübergänge, dar. An jedem Pfeil stehen die Bedingungen, unter denen der Übergang erfolgt.

Eine weitere Darstellungsform ist die Übergangs- oder Zustandsübergangstabelle. Sie ordnet jeder Kombination aus momentanem Zustand und Eingabesymbol den nächsten Zustand zu. Zustandstabellen können zusätzlich die vollständigen Informationen über die Ausgaben enthalten.

Grundsätzlich werden zwei Gruppen unterschieden:

• Akzeptoren erkennen und akzeptieren Eingaben. Das Ergebnis wird durch den erreichten Zustand signalisiert. Als Eingaben dienen gewöhnlich Symbole oder Buchstaben. Ein Beispiel ist ein Automat, der das Wort „gut“ erkennt. Akzeptoren kommen vor allem in der Wort- und Spracherkennung zum Einsatz.
• Transduktoren erzeugen abhängig von Zustand und Eingabe Ausgaben und werden vor allem für Steuerungsaufgaben verwendet.

Außerdem unterscheidet man deterministische und nichtdeterministische Automaten. Bei einem deterministischen endlichen Automaten (DEA) existiert für jeden Zustand und jede mögliche Eingabe genau ein Übergang. Bei einem nichtdeterministischen endlichen Automaten (NEA) kann es für eine Eingabe keinen, einen oder mehrere Übergänge geben. Ein EA mit nur einem Zustand heißt kombinatorischer EA und verwendet ausschließlich Eingabeaktionen.

Moore- und Mealy-Automaten

Transduktoren werden insbesondere in Moore- und Mealy-Automaten unterteilt.

Beim Moore-Modell hängt die Ausgabe Γ nur vom Zustand S ab: S → Γ. Es werden Eingangsaktionen verwendet. Dadurch ist das Verhalten meist einfacher und leichter verständlich. Beim Beispiel einer Aufzugtür gibt es die Befehle „aufmachen“ und „zumachen“. Beim Eintritt in den Zustand „Aufgehend“ startet ein Motor zum Öffnen der Tür; im Zustand „Zugehend“ läuft er in der entgegengesetzten Richtung. In den Zuständen „Auf“ und „Zu“ wird der Motor angehalten und die jeweilige Situation nach außen gemeldet.

Beim Mealy-Modell hängt die Ausgabe Γ sowohl vom Zustand S als auch von der Eingabe Σ ab: S × Σ → Γ. Eingabeaktionen können etwa beim Befehl „zumachen“ den Motor zum Schließen und beim Befehl „aufmachen“ in umgekehrter Richtung starten. Mealy-Automaten benötigen häufig weniger Zustände als entsprechende Moore-Automaten, sind aber oft schwieriger zu verstehen.

Wenn das zeitliche Verhalten außer Betracht bleibt, sind Moore- und Mealy-Automaten gleichwertig und können ineinander umgewandelt werden. In der Praxis kommen auch Mischmodelle vor. Beim synchronen Systemdesign in der Digitalelektronik bestehen jedoch wichtige Unterschiede hinsichtlich der Zahl der Zustände und der zeitlichen Eigenschaften der erzeugten Kontrollsignale.

Mathematisches Modell

Ein deterministischer Akzeptor wird als 5-Tupel (Q, s, Σ, F, δ) beschrieben:

• Q ist die endliche Zustandsmenge.
• s ist der Startzustand mit s ∈ Q.
• Σ ist das endliche Eingabealphabet, also die Menge der zulässigen Eingabesymbole.
• F ist die Endzustandsmenge mit F ⊂ Q.
• δ ist die Übergangsfunktion. Sie kann durch eine Automatentafel oder einen Zustandsübergangsgraphen dargestellt werden.

Ein Transduktor wird als 7-Tupel (Σ, Γ, S, s₀, F, δ, ω) definiert. Σ ist ein endliches, nicht leeres Eingabealphabet und Γ ein endliches, nicht leeres Ausgabealphabet. S ist eine endliche, nicht leere Zustandsmenge, s₀ ∈ S der Anfangszustand und F ⊂ S die Endzustandsmenge. Die Zustandsübergangsfunktion lautet δ: S × Σ → S. Die Ausgabefunktion ω legt die Ausgabe fest.

Gilt ω: S × Σ → Γ, hängt die Ausgabe von Zustand und Eingabe ab; es handelt sich um ein Mealy-Modell. Gilt dagegen ω: S → Γ, hängt die Ausgabe nur vom Zustand ab; dies ist ein Moore-Modell.

Beispiele, Optimierung und Testfolgen

Das abstrakte Beispiel besitzt die Zustandsmenge S := {q₁, q₂, q₃}, den Startzustand q₁, das Eingabealphabet Σ := {a, b} und das Ausgabealphabet Γ := {0, 1}. Seine Übergangsfunktion ist festgelegt durch δ(q₁,a)=q₃, δ(q₁,b)=q₂, δ(q₂,a)=q₁, δ(q₂,b)=q₂, δ(q₃,a)=q₁ und δ(q₃,b)=q₂. Für die Ausgabefunktion gelten ω(q₁,a)=0, ω(q₁,b)=1, ω(q₂,a)=1, ω(q₂,b)=1, ω(q₃,a)=0 und ω(q₃,b)=0.

Ein stark vereinfachter Verkaufsautomat hat die Zustände w („warten auf Bezahlung“), a („Bezahlung ausgeführt, warten auf Warenauswahl“) und r („Ware ausgegeben, warten auf Warenentnahme“). Seine Eingabesymbole sind p für „bezahlen“, s für „Ware auswählen“, t für „Ware entnehmen“ und c für „Kauf abbrechen“. Die Übergänge lauten δ(w,p)=a, δ(a,s)=r, δ(a,c)=w und δ(r,t)=w.

Bei der Optimierung sucht man eine Zustandsmaschine mit der geringsten Anzahl von Zuständen, die dieselbe Funktion erfüllt. Dafür können beispielsweise Färbungsalgorithmen eingesetzt werden.

Eine Homing-Folge ist eine Eingabefolge, nach der anhand der Ausgaben bestimmt werden kann, in welchem Zustand sich der Automat anschließend befindet. Bei stark zusammenhängenden Zustandsmaschinen lässt sich damit eine Folge finden, die zum Initialzustand zurückführt. Jede minimale Zustandsmaschine besitzt eine Homing-Folge. Im abstrakten Beispiel führen etwa die Ausgaben nach der Eingabe b unabhängig vom Ausgangszustand zur Zustandsmenge {q₂}.

Eine UIO-Folge (Unique-Input-Output-Folge) dient dagegen dazu, aus den Ausgaben zu bestimmen, in welchem Zustand der Automat gestartet ist. Eine solche Folge existiert nicht immer; das Finden einer UIO-Folge ist PSPACE-vollständig. Für das abstrakte Beispiel werden unter anderem q₁: a/0, a/0, b/1; q₂: a/1 und q₃: b/0 angegeben.

Umsetzung in Hardware und Software

In digitalen Schaltungen können endliche Automaten mit speicherprogrammierbaren Steuerungen, logischen Gattern, Flip-Flops oder Relais aufgebaut werden. Eine Hardwareimplementierung benötigt normalerweise ein Register zum Speichern der Zustandsvariablen, eine Logikeinheit zur Bestimmung der Zustandsübergänge, eine zweite Logikeinheit für die Ausgabe sowie einen Taktgeber oder ein Verzögerungsglied. Dadurch lassen sich vorheriger, aktueller und nachfolgender Zustand unterscheiden und nacheinander schalten.

In der Softwareentwicklung werden Anwendungen unter anderem als ereignisgesteuerte endliche Automaten oder als virtuelle endliche Automaten modelliert und implementiert.

Da reale digitale Computer nur eine endliche Speichergröße besitzen, können sie nur eine endliche, wenn auch sehr große Zahl digitaler Schaltzustände annehmen. Deshalb lassen sie sich als Teilmenge der endlichen Automaten auffassen. Für theoretische Untersuchungen ist es jedoch häufig zweckmäßiger, sie leistungsfähigeren Automatenmodellen wie der Turingmaschine zuzuordnen.