0 Daumen
124 Aufrufe

blob.png

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.

von

1 Antwort

0 Daumen

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.

von 5,5 k

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

+1 Daumen
1 Antwort
0 Daumen
1 Antwort
0 Daumen
1 Antwort

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community