Was ist das Pumping Lemma in Laienbegriffen?

Ich sah diese Frage und war neugierig, was das Pump-Lemma war ( Wikipedia half nicht viel).

Ich verstehe, dass es im Grunde ein theoretischer Beweis ist, der wahr sein muss, damit eine Sprache in einer bestimmten Klasse ist, aber darüber hinaus verstehe ich es nicht wirklich.

Möchte jemand versuchen, es auf einer ziemlich detaillierten Ebene auf eine Weise zu erklären, die für Nicht-Mathematiker / Doktoranden verständlich ist?

Das Pump-Lemma ist ein einfacher Beweis dafür, dass eine Sprache nicht regulär ist, was bedeutet, dass keine Finite-State-Maschine dafür gebaut werden kann. Das kanonische Beispiel ist die Sprache (a^n)(b^n). Dies ist die einfache Sprache, die nur eine beliebige Anzahl von as ist, gefolgt von der gleichen Anzahl von bs. Also die Saiten

ab
aabb
aaabbb
aaaabbbb

etc. sind in der Sprache, aber

aab
bab
aaabbbbbb

usw. sind nicht.

Es ist einfach genug, ein FSM für diese Beispiele zu erstellen:

Dieser funktioniert bis zu n = 4. Das Problem ist, dass unsere Sprache n nicht eingeschränkt hat und endliche Zustandsmaschinen endlich sein müssen. Egal wie viele Zustände ich zu dieser Maschine hinzufüge, jemand kann mir eine Eingabe geben, wobei n gleich der Anzahl von Zuständen plus eins ist und meine Maschine ausfällt. Wenn also eine Maschine zum Lesen dieser Sprache gebaut werden kann, muss irgendwo eine Schleife vorhanden sein, um die Anzahl der Zustände endlich zu halten. Mit diesen Schleifen hinzugefügt:

Alle Zeichenfolgen in unserer Sprache werden akzeptiert, aber es gibt ein Problem. Nach den ersten vier aSekunden verliert die Maschine die Anzahla eingegebenen Sekunden, da sie im selben Zustand bleibt. Das bedeutet, dass ich nach vier beliebig viele as zur Zeichenfolge hinzufügen kann, ohne bs hinzuzufügen , und trotzdem den gleichen Rückgabewert erhalte. Dies bedeutet, dass die Zeichenfolgen:

aaaa(a*)bbbb

mit (a*) über eine beliebige Anzahl von a, s wird alle von der Maschine übernommen werden , obwohl sie offensichtlich nicht alle in der Sprache. In diesem Zusammenhang würden wir sagen, dass der Teil des Strings (a*)gepumpt werden kann. Die Tatsache, dass die endliche Zustandsmaschine endlich ist und n nicht begrenzt ist, garantiert, dass jede Maschine, die alle Zeichenfolgen in der Sprache akzeptiert, diese Eigenschaft haben MUSS. Die Maschine muss irgendwann eine Schleife ausführen, und an der Stelle, an der die Schleife ausgeführt wird, kann die Sprache gepumpt werden. Daher kann für diese Sprache keine Finite-State-Machine erstellt werden, und die Sprache ist nicht regulär.

Denken Sie daran, dass reguläre Ausdrücke und Maschinen mit endlichem Status gleichwertig sind. Ersetzen aund bschließen Sie dann HTML-Tags, die ineinander eingebettet werden können, und sehen Sie, warum es nicht möglich ist, HTML-Tags mit regulären Ausdrücken zu analysieren

Es ist ein Gerät, das beweisen soll, dass eine bestimmte Sprache nicht einer bestimmten Klasse angehören kann.

Betrachten wir die Sprache der ausgeglichenen Klammern (dh die Symbole '(' und ')' und einschließlich aller Zeichenfolgen, die in der üblichen Bedeutung ausgeglichen sind und keine, die dies nicht sind). Wir können das Pump-Lemma verwenden, um zu zeigen, dass dies nicht regelmäßig ist.

(Eine Sprache ist eine Reihe möglicher Zeichenfolgen. Ein Parser ist eine Art Mechanismus, mit dem wir feststellen können, ob sich eine Zeichenfolge in der Sprache befindet. Daher muss er in der Lage sein, den Unterschied zwischen einer Zeichenfolge in der Sprache und einer Zeichenfolge außerhalb zu erkennen Die Sprache. Eine Sprache ist "normal" (oder "kontextfrei" oder "kontextsensitiv" oder was auch immer), wenn es einen regulären (oder was auch immer) Parser gibt, der sie erkennen kann und zwischen Zeichenfolgen in der Sprache und Zeichenfolgen in der Sprache unterscheidet die Sprache.)

LFSR Consulting hat eine gute Beschreibung geliefert. Wir können einen Parser für eine reguläre Sprache als endliche Sammlung von Kästchen und Pfeilen zeichnen, wobei die Pfeile Zeichen darstellen und die Kästchen sie verbinden (als "Zustände" fungieren). (Wenn es komplizierter ist, ist es keine reguläre Sprache.) Wenn wir eine Zeichenfolge erhalten können, die länger als die Anzahl der Felder ist, bedeutet dies, dass wir ein Feld mehr als einmal durchlaufen haben. Das heißt, wir hatten eine Schleife und können die Schleife so oft durchlaufen, wie wir möchten.

Wenn wir für eine reguläre Sprache eine beliebig lange Zeichenfolge erstellen können, können wir sie in xyz unterteilen, wobei x die Zeichen sind, die wir zum Beginn der Schleife benötigen, y die eigentliche Schleife ist und z das ist, was auch immer wir sind müssen die Zeichenfolge nach der Schleife gültig machen. Wichtig ist, dass die Gesamtlängen von x und y begrenzt sind. Wenn die Länge größer als die Anzahl der Boxen ist, haben wir dabei offensichtlich eine andere Box durchlaufen, und so gibt es eine Schleife.

In unserer ausgewogenen Sprache können wir also zunächst eine beliebige Anzahl linker Klammern schreiben. Insbesondere können wir für einen bestimmten Parser mehr linke Parens schreiben als Kästchen, sodass der Parser nicht erkennen kann, wie viele linke Parens es gibt. Daher ist x eine gewisse Anzahl von linken Parens, und dies ist festgelegt. y ist auch eine Anzahl von linken Parens, und dies kann auf unbestimmte Zeit zunehmen. Wir können sagen, dass z eine Anzahl von richtigen Parens ist.

Dies bedeutet, dass wir möglicherweise eine Zeichenfolge von 43 linken und 43 rechten Parens haben, die von unserem Parser erkannt werden, aber der Parser kann dies nicht anhand einer Zeichenfolge von 44 linken und 43 rechten Parens erkennen, die nicht in unserer Sprache enthalten ist Der Parser kann unsere Sprache nicht analysieren.

Da jeder mögliche reguläre Parser eine feste Anzahl von Feldern hat, können wir immer mehr linke Parens schreiben, und durch das Pump-Lemma können wir dann mehr linke Parens auf eine Weise hinzufügen, die der Parser nicht erkennen kann. Daher kann die ausgeglichene Sprache in Klammern nicht von einem regulären Parser analysiert werden und ist daher kein regulärer Ausdruck.

Es ist schwierig, es für Laien zu verstehen, aber im Grunde sollten reguläre Ausdrücke eine nicht leere Teilzeichenfolge enthalten, die so oft wiederholt werden kann, wie Sie möchten, während das gesamte neue Wort für die Sprache gültig bleibt.

In der Praxis reichen Pump-Lemmas nicht aus, um eine korrekte Sprache zu beweisen, sondern um einen Beweis durch Widerspruch zu erbringen und zu zeigen, dass eine Sprache nicht in die Klasse der Sprachen (regulär oder kontextfrei) passt, indem das Pump-Lemma gezeigt wird nicht dafür arbeiten.

Grundsätzlich haben Sie eine Definition einer Sprache (wie XML), mit der Sie feststellen können, ob eine bestimmte Zeichenfolge (ein "Wort") Mitglied dieser Sprache ist oder nicht.

Das Pump-Lemma legt eine Methode fest, mit der Sie ein "Wort" aus der Sprache auswählen und dann einige Änderungen daran vornehmen können. Der Satz besagt, dass, wenn die Sprache regelmäßig ist, diese Änderungen ein "Wort" ergeben sollten, das immer noch aus derselben Sprache stammt. Wenn das Wort, das Sie sich einfallen lassen, nicht in der Sprache ist, könnte die Sprache überhaupt nicht regulär gewesen sein.

Das einfache Pump-Lemma ist das für reguläre Sprachen, bei denen es sich unter anderem um Stringsätze handelt, die von endlichen Automaten beschrieben werden. Das Hauptmerkmal einer endlichen Automatisierung ist, dass sie nur eine endliche Speichermenge hat, die durch ihre Zustände beschrieben wird.

Angenommen, Sie haben eine Zeichenfolge, die von einem endlichen Automaten erkannt wird und die lang genug ist, um den Speicher der Automatisierung zu "überschreiten", dh in der sich Zustände wiederholen müssen. Dann gibt es einen Teilstring, bei dem der Zustand des Automaten am Anfang des Teilstrings der gleiche ist wie der Zustand am Ende des Teilstrings. Da das Lesen des Teilstrings den Status nicht ändert, kann er beliebig oft entfernt oder dupliziert werden, ohne dass der Automat klüger ist. Daher müssen diese modifizierten Zeichenfolgen auch akzeptiert werden.

Es gibt auch ein etwas komplizierteres Pump-Lemma für kontextfreie Sprachen, bei dem Sie an zwei Stellen in der Zeichenfolge entfernen / einfügen können, was intuitiv als übereinstimmende Klammern angesehen werden kann.

Per Definition sind reguläre Sprachen diejenigen, die von einem endlichen Automaten erkannt werden. Stellen Sie sich das als Labyrinth vor: Zustände sind Räume, Übergänge sind Einbahnstraßen zwischen Räumen, es gibt einen Anfangsraum und einen Ausgangsraum (Endraum). Wie der Name "endlicher Zustandsautomat" sagt, gibt es eine endliche Anzahl von Räumen. Jedes Mal, wenn Sie einen Korridor entlang fahren, notieren Sie den Brief an der Wand. Ein Wort kann erkannt werden, wenn Sie einen Pfad vom Anfang zum letzten Raum finden, der in der richtigen Reihenfolge durch die mit den Buchstaben gekennzeichneten Korridore führt.

Das Pump-Lemma besagt, dass es eine maximale Länge (die Pumplänge) gibt, für die Sie durch das Labyrinth wandern können, ohne jemals in einen Raum zurückzukehren, durch den Sie zuvor gegangen sind. Die Idee ist, dass Sie, da es nur so viele verschiedene Räume gibt, in die Sie gehen können, ab einem bestimmten Punkt entweder das Labyrinth verlassen oder Ihre Spuren überqueren müssen. Wenn Sie es schaffen, einen längeren Weg als diese Pumplänge im Labyrinth zu gehen, machen Sie einen Umweg: Sie fügen einen (mindestens einen) Zyklus in Ihren Weg ein, der entfernt werden könnte (wenn Sie möchten, dass Sie das Labyrinth überqueren) ein kleineres Wort erkennen) oder auf unbestimmte Zeit wiederholen (gepumpt) (um ein super langes Wort zu erkennen).

Es gibt ein ähnliches Lemma für kontextfreie Sprachen. Diese Sprachen können als Wort dargestellt werden, das von Pushdown-Automaten akzeptiert wird. Hierbei handelt es sich um Automaten mit endlichem Zustand, die mithilfe eines Stapels entscheiden können, welche Übergänge ausgeführt werden sollen. Da es jedoch immer noch eine begrenzte Anzahl von Zuständen gibt, überträgt sich die oben erläuterte Intuition, selbst wenn der formale Ausdruck der Eigenschaft etwas komplexer sein kann .

In Laienbegriffen denke ich, dass Sie es fast richtig haben. Es ist eine Beweismethode (eigentlich zwei), um zu beweisen, dass eine Sprache NICHT in einer bestimmten Klasse ist.

Betrachten Sie beispielsweise eine reguläre Sprache (regulärer Ausdruck, Automaten usw.) mit einer unendlichen Anzahl von Zeichenfolgen. An einem bestimmten Punkt, wie starblue sagte, geht Ihnen der Speicher aus, weil die Zeichenfolge für den Automaten zu lang ist. Dies bedeutet, dass es einen Teil der Zeichenfolge geben muss, den der Automat nicht erkennen kann, wie viele Kopien davon Sie haben (Sie befinden sich in einer Schleife). Also, eine beliebige Anzahl von Kopien dieses Teilstrings in der Mitte des Strings, und Sie sind immer noch in der Sprache.

Dies bedeutet , dass wenn Sie eine Sprache haben , das diese Eigenschaft nicht hat, das heißt, es ist eine ausreichend lange Zeichenfolge mit NO String , dass Sie beliebig oft wiederholen können und immer noch in der Sprache sein, dann ist die Sprache nicht regulär.

Nehmen wir zum Beispiel diese Sprache L = a ⁿ b ⁿ .

Versuchen Sie nun, einen endlichen Automaten für die obige Sprache für einige n zu visualisieren .

wenn n = 1 ist, ist der String w = ab . Hier können wir einen endlichen Automaten ohne Schleife machen, wenn n = 2 ist, der String w = a ² b ² . Hier können wir einen endlichen Automaten ohne Schleife machen

wenn n = p , ist der String w = a ^p b ^p . Grundsätzlich kann ein endlicher Automat mit 3 Stufen angenommen werden. In der ersten Stufe werden eine Reihe von Eingaben vorgenommen und die zweite Stufe betreten. Ähnlich von Stufe 2 bis Stufe 3. Nennen wir diese Stufen x , y und z .

Es gibt einige Beobachtungen

1. Auf jeden Fall enthält x 'a' und z 'b'.
2. Jetzt müssen wir uns über y klar sein :
   • Fall a : y darf nur 'a' enthalten
   • Fall b : y darf nur 'b' enthalten
   • Fall c : y kann eine Kombination aus 'a' und 'b' enthalten.

Die endlichen Automatenzustände für Stufe y sollten also in der Lage sein, Eingaben 'a' und 'b' aufzunehmen, und es sollten auch nicht mehr a und b genommen werden, die nicht zählbar sind.

1. Wenn Stufe y nur ein 'a' und ein 'b' annimmt, sind zwei Zustände erforderlich
2. Wenn zwei 'a' und ein 'b' benötigt werden, sind drei Zustände ohne Schleifen usw. erforderlich.

Das Design der Stufe y ist also rein unendlich. Wir können es nur durch Setzen einiger Schleifen endlich machen, und wenn wir Schleifen setzen, kann der endliche Automat Sprachen jenseits von L = a ⁿ b ⁿ akzeptieren . Für diese Sprache können wir also keinen endlichen Automaten konstruieren. Daher ist es nicht regelmäßig.

Dies ist keine Erklärung als solche, aber es ist einfach. Für a ^ nb ^ n sollte unser FSM so aufgebaut sein, dass b die Anzahl der bereits analysierten a kennen muss und die gleiche n Anzahl von b akzeptiert. Ein FSM kann so etwas nicht einfach machen.