Warum verwendet das Pumping-Lemma für kontextfreie Sprachen uvwxy, das für reguläre uvw?

Grundsätzlich sagt der Titel. Warum können Sie den Teil "xy" "ignorieren", wenn Sie beweisen möchten, ob eine Sprache regulär ist?

Beide Pump-Lemmas haben eine intuitive Erklärung in Bezug auf einen Automaten, der eine Sprache erkennen kann.

Eine reguläre Sprache kann von einem endlichen Automaten erkannt werden. Alle Wörter werden erkannt durch:

• entweder ein endlicher Weg durch den Automaten: Wörter, die kürzer als die Pumplänge sind;
• oder ein Pfad, der durch einen Knoten verläuft, an dem sich eine Schleife befindet. In diesem Fall ist es möglich, die Schleife beliebig oft zu durchlaufen: Dies ist der Teil, wobei der Pfad durch eine Runde der Schleife ist und ist die Anzahl der Lops.$y^n$$y$$n$

Eine kontextfreie Sprache kann von einem Pushdown-Automaten erkannt werden. Alle Wörter werden erkannt durch:

• entweder ein endlicher Weg durch den Automaten: Wörter, die kürzer als die Pumplänge sind;
• oder ein Pfad, der sowohl eine Schleife mit Pushs zum Stapel als auch eine andere Schleife mit entsprechenden Pops enthält. Pushs und Pops müssen ausgeglichen sein, um am Ende einen leeren Stapel zu erhalten. Dann enthält das Wort eine Schleife mit Push , einen weiteren Pfad und eine Schleife mit Pops . Die Anzahl der Läufe durch die beiden Schleifen muss gleich sein, kann aber eine beliebige Anzahl sein, daher das mittlere Bit .$v$$w$$x$$v^n w x^n$

Eine ähnliche Intuition erhalten Sie auch durch die Art und Weise, wie reguläre und kontextfreie Sprachen durch einen regulären Ausdruck bzw. eine kontextfreie Grammatik angegeben werden können.

Wenn ein Wort durch einen regulären Ausdruck erkannt wird, gilt Folgendes:

• Entweder verwendet das Wort einen Teil des Ausdrucks unter dem Operator (Kleene-Stern), und dieser Teil kann beliebig oft wiederholt werden.$^*$$y$
• oder das Wort verwendet keinen Teil des Ausdrucks unter einem Stern und kann nicht länger als der Ausdruck selbst sein.

Wenn ein Wort von einer kontextfreien Grammatik erkannt wird, dann:

• Es kann sein, dass das Wort von einem Analysebaum erkannt wird, in dem ein Teilbaum ist, der vom Nichtterminal erkannt wird , und ein Teilbaum dieses Teilbaums von demselben Nichtterminal erkannt wird . In diesem Fall sei der Teil des Wortes, der von , und der Teil, der von erkannt wird . Sie erhalten auch einen gültigen Analysebaum, wenn Sie durch ersetzen oder umgekehrt. Da nach dem Ersetzen enthält$\mathcal{T}_1$$A$$\mathcal{T}_0$$A$$w$$\mathcal{T}_0$$vwx$$\mathcal{T}_1$$\mathcal{T}_1$$\mathcal{T}_0$$\mathcal{T}_1$$\mathcal{T}_0$$\mathcal{T}_0$ durch können Sie die Kopie von in durch ersetzen und so weiter. Dies bedeutet, dass Sie durch , , usw. ersetzen und trotzdem ein Wort mit einem gültigen Analysebaum erhalten können.$\mathcal{T}_1$$\mathcal{T}_0$$\mathcal{T}_1$$\mathcal{T}_1$$vwx$$w$$v^2wx^2$$v^3wx^3$
• Andernfalls gibt es keinen Teilbaum des Analysebaums, der dasselbe Nichtterminal wiederverwendet, und in diesem Fall ist die Länge des Wortes begrenzt, da die Tiefe des Analysebaums durch die Anzahl der Nichtterminale in der Grammatik begrenzt ist.

Das liegt an der "Struktur" der Sprachen, die von den jeweiligen Pump-Lemmas beobachtet wird. Schauen Sie sich die Proofs der jeweiligen Pumpenergebnisse an.

Für reguläre Sprachen ist die Struktur linear, und für jedes lange Wort gibt es einen Zustand, der bei der akzeptierenden Berechnung eines Automaten mit endlichen Zuständen zweimal wiederholt wird. Die zwischen diesen Zuständen gelesene Zeichenfolge kann wiederholt werden.

Die Struktur kontextfreier Sprachen ist verschachtelt und baumartig. Wiederum hat ein langes Wort einen Ableitungsbaum, der ein Nichtterminal auf einem der Pfade im Baum wiederholt. Diese Struktur kann auch wiederholt werden, generiert jedoch zwei Zeichenfolgen, sowohl links als auch rechts.

Das Pump-Lemma für kontextfreie Sprachen ist im Kern eine Anwendung des Pigeonhole-Prinzips. Wenn wir ein ausreichend langes Wort in der Sprache nehmen und einen seiner Analysebäume betrachten, gibt es einen Pfad, auf dem sich eines der Nichtterminals wiederholt. Auf diese Weise können wir einen Teil des Wortes durch Ausschneiden und Einfügen "pumpen".

Betrachten Sie als Beispiel den folgenden Analysebaum:

Die sich wiederholenden nicht terminale ist . Wir können die Wiederholung beseitigen, um den Analysebaum zu erhalten:$A$

Wir können auch die Wiederholung "pumpen", um den Analysebaum zu erhalten:

In Bezug auf die Wörter selbst haben wir mit dem Wort und zuerst das Wort erhalten$sabacabas$$sacas$ und dann das Wort $sababacababas$.

Das Pumpen entspricht dem Variieren der Anzahl der Anwendungen der Ableitung $A \Rightarrow^* abAba$. Sie können sehen, dass zwei verschiedene Teile gleichzeitig gepumpt werden. Dies ist notwendig für Sprachen wie$\{a^n b^n : n \geq 0\}$: das $a$ und $b$ Teile müssen separat gepumpt werden.

Überlegen Sie nun, was passiert, wenn wir dieselben Argumente auf eine linke reguläre Grammatik anwenden :

Da die Grammatik regelmäßig belassen wird, erfolgt die gepumpte Ableitung $A \Rightarrow^* abA$enthält nur ein gepumptes Teil. Dies ist aufgrund der Form der Analysebäume bei linken regulären Grammatiken immer der Fall.

In Bezug auf die Zersetzung $uvwxy$Dies impliziert, dass $x = \epsilon$, und so $uv^iwx^iy = uv^iwy$Dies ist genau die Form des Pump-Lemmas für reguläre Sprachen (unter Berücksichtigung $wy$als ein einziges Wort). Die besondere Form der Analysebäume in der linken regulären Grammatik ermöglicht es uns, ein stärkeres Pump-Lemma zu erhalten.

Gutschrift: Alle mit dem Syntax Tree Generator gezeichneten Analysebäume .