ω-Automat

Ein ω-Automat (Omega-Automat) ist ein mathematisches Modell, das eine Erweiterung des endlichen Automaten auf die Eingabe unendlicher Wörter darstellt. Endlich heißt der Automat deshalb, weil die Anzahl seiner inneren Zustände endlich ist. Ebenso ist das Alphabet, über dem dieser Automat arbeitet, endlich.

Der griechische Buchstabe ω (omega) steht hier für die kleinste unendliche Ordinalzahl.

Motiviert wird die Betrachtung solcher Automaten durch viele Systeme (zum Beispiel Betriebssysteme), die per definitionem eigentlich nicht terminieren sollen, sondern unendlich lange betrieben werden.