Endlicher Automat
Endlicher Automat (EA, engl. finite state machine - FSM) oder Zustandsmaschine ist ein Modell des Verhaltens, bestehend aus Zuständen, Zustandsübergängen und Aktionen. Ein Zustand speichert die Information über die Vergangenheit, d.h. er reflektiert die Änderungen der Eingabe seit dem Systemstart bis zum aktuellen Zeitpunkt. Ein Zustandsübergang zeigt eine Änderung des Zustandes des EA und wird durch logische Bedingungen beschrieben, die erfüllt sein müssen, um den Übergang zu ermöglichen. Eine Aktion ist die Ausgabe des EA, die in einer bestimmten Situation erfolgt. Es gibt vier Typen von Aktionen
- Eingangsaktion
- Ausgabe wird beim Eintreten in einen Zustand generiert
- Ausgangsaktion
- Ausgabe wird beim Verlassen eines Zustandes generiert
- Eingabeaktion
- Ausgabe wird abhängig vom aktuellen Zustand und Eingabe generiert
- Übergangsaktion
- Ausgabe wird abhängig von einem Zustandsübergang generiert
Ein EA kann als Zustandsdiagramm (bzw. Zustandsübergangsdiagramm) wie in Abbildung 1 dargestellt werden. Zusätzlich werden mehrere Typen von Übergangstabellen (bzw. Zustandsübergangstabellen) benutzt. Die folgende Tabelle zeigt eine sehr verbreitete Form von Übergangstabelle: die Kombination aus dem aktuellen Zustand (B) und Eingabe (Y) führt zum nächsten Zustand (C). Die komplette Information über die möglichen Aktionen wird mit Hilfe von Fußnoten angegeben. Eine Definition des EA, die auch die volle Ausgabeinformation beinhaltet, ist mit Zustandstabellen möglich, die für jeden Zustand einzeln definiert werden (siehe auch virtueller EA).
| Momentaner Zustand/ Bedingung |
Zustand A | Zustand B | Zustand C |
| Bedingung X | ... | ... | ... |
| Bedingung Y | ... | Zustand C | ... |
| Bedingung Z | ... | ... | ... |
Die Definition des EA wurde ursprünglich in der Automatentheorie eingeführt und später in der Computertechnik übernommen.
Zustandsmaschinen werden hauptsächlich in der Entwicklung digitaler Schaltungen, Modellierung des Applikationsverhaltens (Steuerungen), generell in der Softwaretechnik sowie Wort- und Spracherkennung benutzt.
Klassifizierung
Generell werden zwei Gruppen von EA unterschieden: Akzeptoren und Transducer.
Akzeptoren
Sie akzeptieren bzw. erkennen die Eingabe und signalisieren durch ihren Zustand das Ergebnis nach Außen. In der Regel werden Symbole (Buchstaben) als Eingabe benutzt. Das Beispiel in der Abbildung 2 zeigt einen EA, der das Wort „gut“ akzeptiert. Akzeptoren werden vorwiegend in der Wort und Spracherkennung eingesetzt.
Transducer
Transducer generieren Ausgabe in Abhängigkeit vom Zustand und Eingabe mit Hilfe von Aktionen. Sie werden vorwiegend für Steuerungsaufgaben eingesetzt, wobei grundsätzlich zwei Typen unterschieden werden:
- Moore Automat
- Im Moore Modell werden nur Eingangsaktionen benutzt, d.h. die Ausgabe hängt nur vom Zustand ab. Das Verhalten eines Moore Automaten ist dadurch einfacher und leichter zu verstehen verglichen mit dem Mealy Modell. Das Beispiel in der Abbildung 3 zeigt einen Moore EA, der eine Aufzugstür steuert. Die Zustandsmaschine kennt zwei Befehle: "aufmachen" und "zumachen", die von einem Benutzer eingegeben werden können. Die Eingangsaktion (E:) im Zustand "Aufgehend" startet einen Motor, der die Tür öffnet und die Eingangsaktion im Zustand "Zugehend" startet den Motor in entgegen gesetzter Richtung. In den Zuständen "Auf" und "Zu" werden keine Aktionen durchgeführt. Sie signalisieren nur die Situation nach Außen (bzw. zu anderen EA).
- Mealy Automat
- Im Mealy Modell werden nur Eingabeaktionen benutzt, d.h. die Ausgabe hängt vom Zustand und Eingabe ab. Einsatz von Mealy Automaten führt oft zu einer Reduktion der Anzahl der notwendigen Zustände. Die Funktion des EA ist dadurch komplexer und oft schwieriger zu verstehen. Das Beispiel in der Abbildung 4 zeigt einen Mealy EA, der das gleiche Verhalten wie in dem Moore Beispiel aufweist. Es gibt zwei Eingabeaktionen (I:): "starte den Motor, um die Tür zu schließen, wenn die Eingabe 'zumachen' erfolgt" und "starte den Motor in entgegengesetzter Richtung, um die Tür zu öffnen, wenn die Eingabe 'aufmachen' erfolgt".
In der Praxis werden meistens Mischmodelle benutzt.
Eine weitere Klassifizierung der EA wird durch die Unterscheidung zwischen deterministischen (DEA) und nicht-deterministischen (NEA) Automaten gemacht. In den deterministischen Automaten existiert für jeden Zustand genau ein Übergang für jede mögliche Eingabe. Bei den nicht-deterministischen Automaten kann es keinen oder auch mehr als einen Übergang für die mögliche Eingabe geben.
Ein EA der nur aus einem Zustand besteht wird als kombinatorischer EA bezeichnet. Er benutzt nur Eingabeaktionen.
Die Logik des EA
Der nächste Zustand und die Ausgabe des EA ist eine Funktion der Eingabe und des aktuellen Zustandes. Abbildung 5 zeigt den Ablauf der Logik.
Das Mathematische Modell
Es gibt unterschiedliche Definitionen, je nach Typ des EA. Ein Akzeptor ist ein 5-Tupel <Σ, S, s0, δ, F>, wo:
- Σ ist das Eingabealphabet (eine endliche nicht leere Menge von Symbolen),
- S ist eine endliche nicht leere Menge von Zuständen,
- s0 ist der Anfangszustand und ein Element aus S,
- δ ist die Zustandsübergangsfunktion: δ = S x Σ → S,
- F ist die Menge von Endzuständen und eine (möglicherweise leere) Untermenge von S.
Ein Transducer ist ein 6-Tupel <Σ, Γ, S, s0, δ, ω>, wo:
- Σ ist das Eingabealphabet (eine endliche nicht leere Menge von Symbolen),
- Γ ist das Ausgabealphabet (eine endliche nicht leere Menge von Symbolen),
- S ist eine endliche nicht leere Menge von Zuständen,
- s0 ist der Anfangszustand und ein Element aus S,
- δ ist die Zustandsübergangsfunktion: δ: S x Σ → S,
- ω ist die Ausgabefunktion.
Falls die Ausgabefunktion eine Funktion von Zustand und Eingabealphabet ist (ω: S x Σ → Γ), dann handelt es sich um ein Mealy Modell. Falls die Ausgabefunktion nur vom Zustand abhängt (ω: S → Γ), dann ist es ein Moore Automat.
Optimierung
Ein EA wird optimiert, indem die Zustandsmaschine mit der geringsten Anzahl von Zuständen gefunden wird, die die gleiche Funktion erfüllt. Dieses Problem kann zum Beispiel mit Hilfe von Färbungsalgorithmen gelöst werden.
Implementation
Hardware Applikationen
In digitalen Schaltungen werden EA mit Hilfe von PLC, logischen Gater, Flip-Flops oder Relays gebaut. Eine Hardwareimplementation benötigt normalerweise ein Register um die Zustandsvariable zu speichern, eine Logikeinheit, die die Zustandsübergänge bestimmt und eine zweite Logikeinheit, die für die Ausgabe verantwortlich ist.
Software Applikationen
In der Softwareentwicklung werden meist folgende Konzepte verwendet, um Applikationen mit Hilfe von Zustandsmaschinen zu modellieren bzw. implementieren:
Endliche Automaten Zeichen
Die allgemeinen Regeln für das Zeichen eines Zustandsübergangsdiagramms sind wie folgt:
- Kreise stellen Zustände dar. Im Kreis steht der Name des Zustands
- Pfeile zwischen Zuständen stellen die Transitionen dar. Auf jedem Pfeil steht, welche Bedingungen den Übergang ermöglichen.
Es gibt Softwarewerkzeuge, um die Graphen der EA in ansprechender Form zu generieren. Beispielsweise kann man die Xy-pic (engl.) oder GasTeX (engl.) Pakete für LaTeX verwenden. Der StateWORKS Editor (engl.) ermöglicht das Zeichen von einzelnen EA sowie Systemen von EA, die dann als JPG Grafiken gespeichert werden können.
Werkzeuge
|
|
|
Siehe auch
Literatur
- Hopcroft, John E. und Ullman, Jeffrey D.: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, ISBN 3-89319-181-X
- Sander, Stucky und Herschel: Automaten, Sprachen, Berechenbarkeit, ISBN 3-519-02937-5
- Kohavi, Z.: Switching and Finite Automata Theory (engl.), McGraw-Hill, 1978.
- Gill, A.: Introduction to the Theory of Finite-state Machines (engl.), McGraw-Hill, 1962.
Weblinks
- Vorlesungsreihe zur Automatentheorie von Wolfgang Thomas, RWTH Aachen
- Datenverarbeitende Systeme - Allgemeine Informationen - Vorlesung von Helmut Knebl, Fachhochschule Nürnberg
- Automaten und Formale Sprachen - Vorlesung von Siegmar Gerber, Universität Leipzig
- Formale Sprachen und Abstrakte Automaten - Kurs von Tino Hempel, Richard-Wossidlo-Gymnasium Ribnitz-Damgarten