Ich versuche zu verstehen, was diese "magische" Zahl "n" ist, die in jeder Anwendung des Pumping-Lemmas verwendet wird. Nach stundenlanger Recherche zu diesem Thema kam ich auf folgende Website: Ссылка
Es heißt
n ist die längste Zeichenfolge kann ohne eine Schleife sein. Das größte n kann be is s, obwohl es für eine bestimmte Sprache kleiner sein könnte.
Von dem, was ich verstehe, wenn es eine Sprache L gibt, ist die Pumplänge von L die Anzahl von Zuständen in den Finite-State-Automaten, die L erkennt. Stimmt das?
Wenn es dann ist, was genau sagt die letzte Zeile von oben "obwohl sie für eine bestimmte Sprache kleiner sein könnte"? Völlige Sauerei in meinem Kopf. Könnte jemand bitte aufklären?
Ein Staat erkennt keine Sprache. Ein DFA erkennt eine Sprache, indem es genau die Wörter in den Sprachen akzeptiert und keine anderen. Ein DFA hat viele Zustände.
Wenn es eine reguläre Sprache L gibt, die durch das Pumping Lemma modelliert werden kann, wird sie eine Eigenschaft n haben.
Für ein DFA mit s-Zuständen muss s, um L akzeptieren zu können, & gt; = n sein.
Die letzte Zeile besagt lediglich, dass es einige Sprachen gibt, in denen s größer als n ist, anstatt gleich.
Dies ist wahrscheinlich besser geeignet für Ссылка oder Ссылка (nicht sicher über den Wert von mir selbst).
Hinweis : Trivialerweise akzeptieren nicht alle DFAs mit ausreichender Anzahl die Sprache. Auch die Tatsache, dass eine Sprache das Pumping-Lemma passiert, bedeutet nicht, dass es regelmäßig ist (aber das Versagen bedeutet definitiv nicht).
Beachten Sie auch, dass die Sprache zwischen FA und DFA wechselt - dies ist ein wenig lasch, aber da NDFAs die gleiche Leistung wie DFAs haben und DFAs einfacher zu schreiben und zu verstehen sind, werden DFAs für den Beweis verwendet.
Bearbeiten Ich gebe ein Beispiel für eine reguläre Sprache, damit Sie eine Idee von u, v, w, z und n sehen können. Dann besprechen wir s.
%Vor%Daher:
%Vor%Daher wird es durch das Pumping Lemma modelliert. Ein DFA benötigt mindestens 4 Status. Also lasst uns an eins denken.
%Vor%4 Staaten, wie erwartet. Nicht möglich, es in weniger zu tun, wie von n = 4 erwartet. In diesem Fall ist das Beispiel ziemlich einfach, also glaube ich nicht, dass man einen mit mehr als 4 Zuständen bauen kann (aber das wäre okay, wenn es nötig wäre) .
Tags und Links automata pumping-lemma