Finite State Machine

Finite State Machine
Abb.1 Beispiel eines EA

Ein endlicher Automat (EA, auch Zustandsmaschine, englisch finite state machine (FSM)) ist ein Modell des Verhaltens, bestehend aus Zuständen, Zustandsübergängen und Aktionen.

Ein Automat heißt endlich, wenn die Menge der Zustände, die er annehmen kann (später S genannt), endlich ist. Ein EA ist ein Spezialfall aus der Menge der Automaten. 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 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 Übergangstabellen: 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 ... ... ...
Übergangstabelle

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.

Inhaltsverzeichnis

Klassifizierung

Generell werden zwei Gruppen von EA unterschieden: Akzeptoren und Transduktoren.

Akzeptoren

Abb. 2 EA vom Typ Akzeptor: erkennt das Wort "gut"

Sie akzeptieren und 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.

Transduktoren (Transducer)

Transduktoren generieren Ausgaben in Abhängigkeit von Zustand und Eingabe mit Hilfe von Aktionen. Sie werden vorwiegend für Steuerungsaufgaben eingesetzt, wobei grundsätzlich zwei Typen unterschieden werden:

Abb. 3 EA vom Typ Transduktor: Moore-Modell
Moore-Automat
Im Moore-Modell werden nur Eingangsaktionen benutzt, d. h., die Ausgabe (Γ) hängt nur vom Zustand (S) ab (S → Γ). Das Verhalten eines Moore-Automaten ist dadurch, verglichen mit dem Mealy-Modell, einfacher und leichter zu verstehen. Das Beispiel in Abbildung 3 zeigt einen Moore-Automaten, der eine Aufzugtü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 entgegengesetzter Richtung. Die Eingangsaktionen in den Zuständen "Auf" und "Zu" halten den Motor an. Sie signalisieren außerdem die Situation nach außen (z.B. zu anderen EA).
Abb. 4 EA vom Typ Transduktor: Mealy-Modell
Mealy-Automat
Im Mealy-Modell werden Eingabeaktionen benutzt, d. h., die Ausgabe (Γ) hängt von Zustand (S) und Eingabe (Σ) ab (S × Σ → Γ). Der Einsatz von Mealy-Automaten führt oft zu einer Verringerung der Anzahl zu berücksichtigender 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 der EA im 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".

Moore- und Mealy-Automaten sind gleichwertig. Der eine kann in den jeweils anderen überführt werden. 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

Abb. 5 Die Logik eines 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 (oder auch deterministischer Automat) ist ein 5-Tupel (Σ, S, s0, δ, F), wobei:

  • Σ 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 Transduktor ist ein 6-Tupel (Σ, Γ, S, s0, δ, ω), wobei:

  • Σ 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.

Siehe auch: Minimierung eines DEA

Implementierung

Hardware

In digitalen Schaltungen werden EA mit Hilfe von PLCs, logischen Gattern, Flip-Flops oder Relais 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

In der Softwareentwicklung werden meist folgende Konzepte verwendet, um Applikationen mit Hilfe von Zustandsmaschinen zu modellieren bzw. implementieren:

Darstellung endlicher Automaten

Die allgemeinen Regeln für das Zeichnen 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.

Siehe auch

Literatur

  • John E. Hopcroft, Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Addison-Wesley, Bonn 1990, ISBN 3-89319-181-X
  • Sander, Stucky, Herschel: Automaten, Sprachen, Berechenbarkeit. Teubner, Stuttgart 1992, ISBN 3-519-02937-5
  • F. Wagner: Modeling Software with Finite State Machines: A Practical Approach. Auerbach, Boca Raton 2006, ISBN 0-8493-8086-3
  • Z. Kohavi: Switching and Finite Automata Theory. McGraw-Hill, New York 1978, ISBN 0-07-035310-7 (englisch)
  • A. Gill: Introduction to the Theory of Finite-state Machines. McGraw-Hill, New York 1962 (englisch)
  • H.-D. Wuttke, K. Henke: Schaltsysteme - Eine automatenorientierte Einführung. Pearson Studium, München 2003, ISBN 3-8273-7035-3

Weblinks


Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Finite-state machine — State machine redirects here. For infinite state machines, see State transition system. For fault tolerance methodology, see State machine replication. SFSM redirects here. For the Italian railway company, see Circumvesuviana. A finite state… …   Wikipedia

  • Finite state machine — A finite state machine (FSM) or finite state automaton (plural: automata ) or simply a state machine, is a model of behavior composed of a finite number of states, transitions between those states, and actions. A finite state machine is an… …   Wikipedia

  • Finite-State-Machine — Abb.1 Beispiel eines EA Ein endlicher Automat (EA, auch Zustandsmaschine, englisch finite state machine (FSM)) ist ein Modell des Verhaltens, bestehend aus Zuständen, Zustandsübergängen und Aktionen. Ein Automat heißt endlich, wenn die Menge der… …   Deutsch Wikipedia

  • finite state machine — baigtinis automatas statusas T sritis automatika atitikmenys: angl. finite automaton; finite state machine vok. endlicher Automat, m; Finalautomat, m rus. конечный автомат, m pranc. automate final, m; automate fini, m; automate terminal, m;… …   Automatikos terminų žodynas

  • Deterministic finite-state machine — An example of a Deterministic Finite Automaton that accepts only binary numbers that are multiples of 3. The state S0 is both the start state and an accept state. In the theory of computation and automata theory, a deterministic finite state… …   Wikipedia

  • Nondeterministic finite-state machine — In the theory of computation, a nondeterministic finite state machine or nondeterministic finite automaton (NFA) is a finite state machine where for each pair of state and input symbol there may be several possible next states. This distinguishes …   Wikipedia

  • Nondeterministic finite state machine — In the theory of computation, a nondeterministic finite state machine or nondeterministic finite automaton (NFA) is a finite state machine where for each pair of state and input symbol there may be several possible next states. This distinguishes …   Wikipedia

  • Event-driven finite state machine — In computation, a finite state machine (FSM) is event driven if the creator of the FSM intends to think of the machine as consuming events or messages. This is in contrast to the parsing theory origins of the term finite state machine where the… …   Wikipedia

  • Extended finite state machine — In a conventional finite state machine, the transition is associated with a set of input Boolean conditions and a set of output Boolean functions. In an extended finite state machine (EFSM) model, the transition can be expressed by an “if… …   Wikipedia

  • Virtual finite state machine — The virtual finite state machine (VFSM) is a concept promoted by [http://www.stateworks.com SW Software] and implemented in their StateWORKS product. A VFSM is a finite state machine (FSM) defined in a virtual environment. The VFSM concept… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”