Ein Deterministischer Endlicher Automat (DEA) ist wie folgt definiert:
- Der Automat hat eine feste Anzahl von verschiedenen Zuständen. Diese werden mit einem Kreis dargestellt und enthalten den Namen des Zustands.
- Genau ein Zustand ist der Startzustand. Dieser wird durch einen kurzen Pfeil gekennzeichnet, dessen Spitze in den Zustand zeigt.
- Mindestens einer der Zustände ist ein Endzustand. Endzustände werden durch Doppelkreise bzw. Doppelellipsen dargestellt.
- Der Automat kann durch Eingaben bedient werden. Die Menge der möglichen Eingaben wird Eingabealphabet genannt. Die Elemente des Eingabealphabets nennt man Eingabezeichen. Die Anzahl der verschiedenen Zeichen ist endlich.
- Bei der Eingabe eines Elements des Eingabealphabets erfolgt stets ein Übergang von einem Zustand 1 in einen Zustand 2. Dieser wird durch einen Pfeil von Zustand 1 nach Zustand 2 dargestellt, wobei über den Pfeil das entsprechende Zeichen des Eingabealphabets geschrieben wird, das den Übergang auslöst. Ein Zustand kann auch auf sich selbst zeigen, was bedeutet, dass der Automat bei der entsprechenden Eingabe im selben Zustand bleibt.
- Von einem Zustand dürfen keine zwei Pfeile mit der gleichen Markierung auf verschiedene Zustände verweisen, d.h. der Übergang von einem Zustand auf einen anderen muss bei jeder Eingabe eindeutig sein (Deterministisch).