ein Zustand, den ein abstrakter deterministischer Automat erreichen kann.

Unter einem abstrakten deterministischen Automaten versteht man ein Quintupel (X, Y, Z, f, g). Dabei ist X die Menge aller Inputs, Y die Menge aller Outputs und Z die Menge aller inneren Zustände des Automaten. Weiterhin sind f : Z × X → Z und g : Z × X → Y Abbildungen. Man geht davon aus, daß der Automat in abzählbar vielen Schritten arbeitet, das heißt, es gibt abzählbar viele Takte t = 1, 2, 3,…, wobei jeder Takt einem Zeitintervall entspricht und pro Takt ein Verarbeitungsschritt ausgeführt wird. Bei jeder Erhöhung des Taktes t um 1 wird das Inputsignal x_t auf x_t+1 gesetzt.

Die Arbeitsweise des Automaten ist dann die folgende. Liegt im Takt t der Zustand z_t vor, und ist x_t das zum Takt t gehörende Inputsignal, so gibt der Automat im Takt t den Output y_t = g(z_t, x_t) aus. Im Takt t + 1 wird er dann den Zustand z_t+1 = f (z_t, x_t) annehmen. Ein Zustand z ∈ Z heißt dann erreichbar, wenn es eine Folge von Verarbeitungsschritten und einen Takt t gibt mit z_t = z.