Unendlich Sprachen in abhängigkeit eines Wortes x mit bestimmten Eigenschaften erkennnen

Question

Text erkannt:

Gegeben sei ein e.a. mit \( n \) Zuständen. Zeigen Sie, dass die vom e.a. akzeptierte Sprache genau dann unendlich ist, falls der e.a. ein Wort \( x \) mit \( n \leq|x| \supsetneqq 2 n \) akzeptiert.

Answer 1

Ein Automat mit \(n\) Zuständen, der ein Wort \(x\) mit \(n\leq |x|\) akzeptiert, ist während des Laufs mindestens zwei mal im gleichen Zustand \(q\). Dann gibt es für jedes \(m\in \mathbb{N}\) einen akzeptierenden Lauf, bei dem der Automat \(m\) mal im Zustand \(q\) ist.

Um vom Zustand \(q\) zurück in den Zusand \(q\) zu kommen, sind höchstens \(n-1\) Zustandsübergänge notwendig.