Endlicher Automat

Ein endlicher Automat ist eine Maschine mit Ein- und Augabebereich und einem Zustandsspeicher, der nur eine endliche Anzahl Zustände speichert. Der Automat liest Zeichen um Zeichen von der Eingabe und legt aufgrund des Eingabezeichens und des inneren Zustandes ein Ausgabezeichen fest. Es gibt verschiedene Arten von endlichen Automaten. Sie werden im Rahmen der Berechenbarkeits-Theorie untersucht. Deterministische endliche Automaten können als Spezialfall von nichtdeterministischen Automaten aufgefasst werden. Jeder nichtdeterministische Automat kann durch einen ebenbürtigen deterministischen Automaten dargestellt werden. Dieser braucht dazu aber mehr Zustände. Endliche Automaten werden im Programmieralltag häufig angewandt

Ein Mealy-Automat ist ein endlicher Automat, der die Ausgabe in Verbindung mit den Zustandsübergängen (Transition) liefert, bei einem Moore-Automat ist mit jeden Zustand eine Ausgabe verknüpft. Automaten, die keine Ausgaben mit den Zuständen oder Transitionen verbunden haben, sondern nur angeben ob ein Endzustand erreicht oder nicht erreicht wird, heißen Endliche Akzeptoren.