Automaten auf unendlichen Wörtern

In diesem Teil beschäftigen wir uns mit der Erkennbarkeit von Mengen von

unendlichen

Folgen von Symbolen durch endliche Automaten. Die Tatsache, dass ein Automat ein unendliches Wort verarbeiten soll, mag auf den ersten Moment unnatürlich erscheinen, wenn man sich vorstellt, dass ein Automat ein Wort vom Anfang zum Ende hin abfährt und dann durch Erreichen eines Zustands signalisiert, ob er das Wort akzeptiert oder nicht. Dies ist aber in Wahrheit nur ein Problem mit der Vorstellung. Mathematisch ist die Akzeptanz eines Wortes durch einen Automaten einfach durch die Existenz eines akzeptierenden Laufs gegeben. Genauso kann man sich bei die Frage stellen, ob ein Automat auf einem gegebenen unendlichen Wort einen akzeptierenden Lauf hat. Läufe auf unendlichen Wörtern können ganz leicht als Erweiterung (ins Unendliche) von Läufen auf endlichen Wörtern erklärt werden. Es bleibt lediglich zu definieren, was daran akzeptierend bzw. verwerfend sein soll. Offensichtlich kann dies nicht sinnvoll durch den letzten Zustand auf dem Lauf erklärt werden, da es einfach keinen letzten mehr gibt. Eine sehr natürliche Erweiterung der Akzeptanz durch Erreichen eines Endzustands ins Unendliche ist die sogenannte

Büchi-Bedingung

: Ein Lauf ist akzeptierend, wenn er immer wieder in einen Endzustand gelangt, wenn also unendlich oft Endzustände durchlaufen werden.