Automat, ein Automat mit endlich vielen Zuständen, bei dem jeder Zustand bei jedem Eingabezeichen mindestens einen Nachfolgezustand besitzt.

Zu jedem endlichen Automaten kann ein äquivalenter vollständiger konstruiert werden, indem ein neuer Zustand q^* eingeführt wird, der kein Endzustand ist. Für alle Zustands-/Eingabepaare ohne Nachfolgezustand wird dann q^* als Nachfolgezustand gesetzt. Besonders für deterministische Automaten erleichtert die Vollständigkeit viele Konstruktionen.