Endlicher Automat

aus GlossarWiki, der Glossar-Datenbank der Fachhochschule Augsburg
Wechseln zu:Navigation, Suche
Dieser Artikel erfüllt die GlossarWiki-Qualitätsanforderungen nicht:
  ★★☆☆☆ Korrektheit: teilweise überprüft
  ★☆☆☆☆ Umfang: zu gering
  ★☆☆☆☆ Quellenangaben: Quellen fehlen großteils
  ☆☆☆☆☆ Quellenqualität: ungenügend
  ★★★☆☆ GlossarWiki-Konformität: gut

1 Definition

Der endlicher Automat (EA) oder die "Finite State Machine" (FSM) ist ein Modell des Verhaltens, bestehend aus Zuständen, Zustandsübergängen und Aktionen. Ein Zustand speichert die Information über die Vergangenheit. Ein Zustandsübergang zeigt eine Änderung des Zustandes des Automaten und wird durch logische Bedingungen beschrieben, die erfüllt sein müssen, um den Übergang zu ermöglichen. Eine Aktion ist die Ausgabe des Automaten, die in einer bestimmten Situation erfolgt, dabei können je nach Komplexität des Automaten verschiedene Aktionen durchgeführt werden. Komplexere Automaten besitzen neben der normalen Eingabeaktion auch noch Eingangs- und eine Ausgangsaktionen. Dies sind Methoden, die immer beim Aufrufen bzw. Verlassen des Zustandes durchgeführt werden.

2 Häufigste Ausprägung (deterministischer EA)

Er zeichnet sich dadurch aus, dass in jeder Situation die Arbeitsweise eindeutig definiert ist und dessen Zustände alle erreichbar sind, d. h., entweder gibt es genau einen Folgezustand oder der Automat stoppt vorzeitig.

3 Anwendung

Im alltägliche Sprachgebrauch sind Automaten Maschinen (Geräte), die auf eine Eingabe hin ganz bestimmte Ausgaben erzeugen. Beispiele sind Getränkeautomaten, Fahrkartenautomaten etc. Die Eingaben werden dabei von den Automaten nur gelesen und interpretiert, nicht aber verändert. Dabei werden die Ein und Ausgaben tabellarisch gespeichert und direkt Verknüpft. In der Informatik werden Automaten vorwiegend dazu verwendet, um synchrone Schaltwerke zu beschreiben oder um mit ihrer Hilfe, neben Grammatiken und Syntaxdiagrammen formale Sprachen und ihre Verarbeitung zu definieren. Der endliche Automat hat zwar seine Wurzeln in der Computerlinguistik er wird allerdings heutzutage in den verschiedensten Bereichen eingesetzt. Hier nur einige Beispiele um die vielfältigen Verwendungsmöglichkeitenaufzuzeigen. Interaktive Systeme können beispielsweise als endliche Automaten dargestellt werden, reale Prozesse im Compilerbau oder bei der Beschreibung digitaler Schaltwerke können modelliert werden, aber auch in so informatikfremden Gebieten wie der Systembiologie wird der endliche Automat verwendet um Rektionsnetzwerke zu modellieren. Das der endliche Automat ein wichtiges Tool darstellt sieht man vor allem daran, dass sogar Compiler existieren z.B. der Xerox-Compiler, die reguläre Ausdrücke in einen endlichen Automaten umwandeln.

4 Quellen

Wikipedia:endlicher Automat