Fachwörterlexikon
Suchen Sie hier nach Definitionen zu Fachbegriffen der elektronischen Datenverarbeitung und Informationstechnik! Derzeit umfasst unsere Datenbank 2638 Begriffe, 351 zugehörige Synonyme und weitere Informationen.

Suchbegriff(e) eingeben:

Optionen:
Exakten Ausdruck suchen
Volltextsuche

Suchhinweise:
Die Groß-/Kleinschreibung der Suchbegriffe spielt keine Rolle. Ungültige Zeichen werden aus den Suchbegriffen entfernt.
Verwenden Sie den Singular des Stichwortes, das Sie suchen!
...was sich hinter dem Begriff Slice verbirgt?
 
Zustandsmaschine
Textinhalt dieses Artikels kopieren
Synonym(e):
Endliche Automaten; Finite State Machine; FSM


Zustandsmaschinen sind mathematische Modelle von einfachen idealen Rechenmaschinen. Die Automatentheorie besitzt viele Anwendungen z.B. bei der Modellierung von Parallelen Prozessen, im Compilerbau oder bei der Beschreibung digitaler Schaltwerke.
Ein "endlicher" Automat ist es deshalb, da er nur eine endliche Zahl innerer Zustände besitzt und letztlich nur Wörter mit endlicher Länge akzeptieren kann. Endliche Automaten können genau die Wörter der so genannten regulären Sprachen erkennen, weswegen sie zur Worterkennung genutzt werden und besonderer zur Erkennung von Wortmengen, die durch reguläre Ausdrücke spezifiziert sind.

Beim Parsen von Dokumenten werden ebenfalls Zustandsmaschinen zur Tokenerkennung eingesetzt, um den Zeichenstrom zu einem Tokenstrom zu kondensieren, auf dem dann das Parsen stattfindet.


Funktion:

Ein endlicher Automat liest eine endliche Symbolfolge (Eingabewort) aus einer endlichen Symbolmenge (Eingabealphabet) und zeigt ob er das Wort akzeptiert oder nicht, indem er hält oder nicht. Ein endlicher Automat mit Ausgabe (Mealy- oder Moore-Automat) schreibt dabei auch, gemäß seiner Programmierung, eine endliche Symbolfolge (Ausgabewort) aus einer Symbolmenge (Ausgabealphabet).

Man kann einen endlichen Automat als endliches Transitionssystem beschreiben. Abhängig vom Programm, welches der Automat implementiert, besitzt er eine kleinere oder größere endliche Anzahl von Zuständen, in welche er schalten kann. Am Anfang befindet er sich in einem speziell ausgezeichneten Startzustand. Beim Lesen des Eingabestromes und beim Schreiben des Ausgabestromes geht der Automat schrittweise vor, wobei in jedem Schritt das jeweils nächste Symbol der Eingabe ausgelesen wird. Mit diesem Eingabesymbol und dem momentanen Zustand produziert wird dann in einem Bearbeitungsschritt eine endliche Ausgabesymbolenfolge (und fortlaufend die Ausgabe) ausgeben und in den neuen Zustand übergegangen.

Neben diesem endlichen Einweg-Automat (1EA), der die Eingabe gleichbleibend von einer Richtung liest, lässt sich auch ein endlicher Zweiweg-Automat (2EA) definieren, der nach dem Lesen eines Symbols den Kopf nach links oder rechts bewegen kann.