Definition: Endliche Automaten

Endliche Automaten sind erkennende Systeme die zur Beschreibung von Sprachen benutzt werden. Ein endlicher Automat kann erkennen, ob ein Wort zu einer Sprache gehört oder nicht. Beschrieben werden endliche Automaten durch einen 5-Tupel EA=(E, S, d, s0, F), wobei:

-       E das Eingabealphabet ist

-       S die Zustandsmenge, also Menge aller Zustände, ist

-       d die Überführungsfunktion von einem Zustand in den nächstes darstellt

-       F die Menge aller Endzustände des endlichen Automaten (EA) sind.

Ein endlicher Automat heißt endlich, weil dessen Zustandsmesse endlich sein muss.