Bedingung für die Unendlichkeit der Sprache eines endlichen Automaten

9

Es gibt einen Satz, der besagt:

Bei einem endlichen Zustandsautomaten mit Zuständen, wenn es eine Zeichenkette deren Länge erfüllt dann ist die vom Automaten akzeptierte Sprache unendlich.nwn≤|w|≤2n- -1

Ich verstehe die Einschränkung , aber ich verstehe nicht, warum die Einschränkung ist da.|w|≥n|w|≤2n- -1

automata finite-automata Rahul Sharma
quelle

Antworten:

5

Im schlimmsten Fall könnte Ihre NFA folgendermaßen aussehen:

Das kleinste für das eine Schleife garantiert wird (wodurch eine unendliche Sprache akzeptiert wird), hat die Größe .w2n- -1

André Souza Lemos
quelle
Wenn ich von q0 beginne und danach von q0 zurückkomme, bedeutet das, dass sich ein Zyklus in der Maschine befindet. Ist es im schlimmsten Fall nicht ausreichend, warum kehren wir in diesem Fall wieder in die Endphase zurück? Soweit ich aus dieser Abbildung verstehe, werden wir diese Schleife einmal pumpen und dann wieder in die Endphase gehen, das heißt Sobald wir in die Endphase eintreten, gehen wir davon aus, dass dies nicht meine Zeichenfolge ist, da sie in einen anderen Zustand zurückgekehrt ist. Wenn sie jedoch wieder in die Endphase zurückkehrt, sind wir sicher, dass dies unsere Zeichenfolge ist, da es eine Schleife gibt gepumpt worden?
Rahul Sharma
Wir versuchen etwas über den Automaten zu beweisen , nämlich dass er eine unendliche Sprache akzeptiert. Bei der Formulierung des Beweises wird eine Zeichenfolge vermutet, deren Größe innerhalb eines bestimmten Intervalls angenommen wird. Wenn der Automat eine Schleife hat, existiert natürlich die Zeichenfolge . Was passiert ist, dass wenn innerhalb dieses Intervalls nicht zu finden ist, die Maschine nicht wie die auf dem Bild sein kann. Entweder hat es keine Schleifen oder es hat keine Endzustände. www
André Souza Lemos
Ich verstehe nur Ihren Punkt. Ich versuche nur, die Obergrenze des Intervalls zu verstehen, warum es 2n-1 ist und warum nicht 2n-x (x kann alles außer 1 sein). In der obigen Abbildung können wir sagen, dass die Schleife qo ist -q1 .... qn-q1 .... qn, richtig (die max. Schleife)? Aber wenn ich wieder q0 bin (q0 ... aq, q0), heißt das nicht, dass es eine Schleife gibt, Das Maximum sollte also n sein, warum addieren wir n-1 zu n (oder warum gehen wir wieder in den Endzustand). Es fällt mir schwer, dies zu erreichen :(. Kann die maximale Schleife q0., q1, q2 sein ..qn, qn-1, qn-1..q0, so etwas?
Rahul Sharma
Die Obergrenze ist weil es nicht schlimmer wird. ist kleiner als , und ich habe Ihnen gerade einen Automaten gezeigt, der Schritte benötigt. Es gibt keinen, der mehr braucht (und die Arbeit erledigt), aber einen, der diesen Betrag benötigt. 2n- -12n- -x2n- -12n- -1
André Souza Lemos
Ich habe es jetzt verstanden. Nur ein kleiner Zweifel. Angenommen, ich habe 4 Zustände in meiner Maschine. Und ich habe den String abc gelesen und den Endzustand erreicht. Dann habe ich d dort gelesen und bin in den Ausgangszustand zurückgekehrt und gehe dann wieder in den Endzustand Mein String wird abcdabc. Wie kann ich dies in ein Pump-Lemma aufteilen und y ^ i, wobei i = 1 ist, dazu bringen, zu zeigen, dass y einmal gepumpt wurde?
Rahul Sharma
5

Die zusätzliche Bedingung ermöglicht es Ihnen, einen einfachen Algorithmus zu schreiben - überprüfen Sie alle Zeichenfolgen mit Längen in diesem Intervall -, um die (Un-) Endlichkeit der akzeptierten Sprache zu bestimmen. Auf diese Weise erhalten Sie einen Beweis dafür, dass diese Eigenschaft entscheidbar ist (was bei den meisten Automatenmodellen mit übermäßiger Leistung nicht der Fall ist).

Raphael
quelle
3

Der vollständige Satz besagt eher eine Äquivalenz als eine Implikation :

nwn≤|w|≤2n- -1

|w|≤2n- -1

Yuval Filmus
quelle