Woher kommen die Längenbeschränkungen des Pump-Lemmas?

8

Für eine Sprache mit der Pumplänge und einer Zeichenfolge sind die Pumpspelzen wie folgt: $L$ $p$ $s\in L$

Reguläre Version : If , dann kann als werden, wobei die folgenden Bedingungen erfüllt sind: $|s| \geq p$ $s$ $xyz$

$|y|\geq 1$
$|xy|\leq p$
$\forall i\geq 0: xy^iz\in L$

Kontextfreie Version : If , dann kann als werden, wobei die folgenden Bedingungen erfüllt sind: $|s| \geq p$ $s$ $uvxyz$

$|vy|\geq 1$
$|vxy|\leq p$
$\forall i\geq 0: uv^ixy^iz\in L$

Meine Frage lautet: Kann jemand kurz und deutlich erklären, wie Regelmäßigkeit (Kontextfreiheit) die oben genannten ersten und zweiten Bedingungen impliziert? Die Pumplänge wird durch (endliche) Eigenschaften (endliche Anzahl von Zuständen bzw. endliche Eigenschaften von Produktionsregeln) bestimmt. Die dritten Eigenschaften garantieren, dass ein Zustand (Produktionsregel) beliebig oft übersprungen oder wiederholt werden kann, aber wo tun die ersten und zweite Bedingungen entstehen? Wie sind sie gerechtfertigt?

formal-languages regular-languages context-free pumping-lemma BlueBomber
quelle

Ich kommentiere, da ich Ihre Frage möglicherweise nicht verstehe, aber es scheint mir offensichtlich, dass Sie das Wort in drei Teile, so , dass , wenn Sie ein Wort mit einer Länge von mindestens haben und . Lassen Sie einfach leer sein, das erste Zeichen und den Rest. Habe ich Ihre Frage völlig falsch verstanden?

p \geq 1

$p \geq 1$

x y z

$xyz$

| y | \geq 1

$|y| \geq 1$

| x y | \leq p

$|xy| \leq p$

x

$x$

y

$y$

z

$z$

Pål GD

@ PålGD, ich finde es im Zusammenhang mit den anderen Bedingungen des Lemmas (Länge des pumpbaren Teilstrings ungleich Null und willkürliche Pumpbarkeit) nicht offensichtlich. Ich stimme zu, es ist offensichtlich, dass eine Zeichenfolge mit einer Länge von mindestens in Teilzeichenfolgen unterteilt werden kann, sodass die erste die Länge , aber die Offensichtlichkeit (für mich) überträgt sich nicht, wenn Sie die anderen Bedingungen beibehalten. Vielleicht sollte ich den ursprünglichen Beitrag klarstellen?

x

$x$

\leq x

$\leq x$

BlueBomber

Nein, angesichts der dritten Bedingung sollte man etwas vorsichtiger sein. Wie Sie bemerkt haben, sagen die ersten beiden Bedingungen nichts Nützliches aus. Wie Sie auch bemerken, sind wir tatsächlich in der Lage zu "pumpen", wenn wir das zwingen , nicht leer zu sein (wie es in der Tat die erste Bedingung besagt).

y

$y$

Pål GD

Ist der kontextfreie PL für Ihre Frage erforderlich? Es ist nicht sehr sinnvoll, einige dieser Bedingungen isoliert zu betrachten.

Raphael

@BlueBomber, in beiden Fällen ohne Bedingung (1) ist das Pumpen sinnlos (kann immer den leeren Teilstring auswählen). Für reguläre Sprachen ist (2) nur, dass in Symbolen der DFA für die Sprache in Zuständen war, und nach dem Pigeonhole-Prinzip, wenn der DFA Zustände hat, muss man wiederholt haben (und Sie können den Zyklus durchlaufen mal, die Saite pumpen).

n

$n$

n + 1

$n + 1$

n

$n$

k

$k$

vonbrand

8

Die erste Bedingung, dh ist eindeutig notwendig, wenn Sie etwas Interessantes sagen möchten: Für gilt trivial und gilt immer. $|y| \geq 1$ $y = \varepsilon$ $xy^iz \in L$

Die zweite Bedingung, dh , ist "willkürlich": Das Lemma sagt immer noch etwas Interessantes, wenn Sie es fallen lassen, und es ist immer noch wahr, weil die Aussage schwächer wird. $|xy| \leq p$

Aber denken Sie daran, wofür wir die Pump-Lemmas verwenden möchten: Wir möchten ein (ausreichend langes) Wort finden, sodass alle gültigen Zerlegungen in nicht pumpen können. Daher ist es sinnvoll, möglichst wenige derartige Zerlegungen zuzulassen. Glück , wie wir, der Beweis des Lemmas Pump ohne weiteres ergibt eine starke Einschränkung, nämlich , dass es hat eine pumpbare Zersetzung sein mit mit konstanter . $x,y,z$ $|xy| \leq p$ $p$

Jetzt müssen wir nur endlich viele Präfixe widerlegen (mit möglicherweise unendlich vielen verschiedenen Fortsetzungen natürlich). Wenn Sie sich Beispielanwendungen ansehen , werden Sie feststellen, dass diese diese Einschränkung stark nutzen. $xy$

Raphael
quelle

1

Bedingung 2 ist auf andere Weise "willkürlich". Zum Beispiel ist ein äquivalentes Lemma gegeben, wenn wir (2) durch ersetzen . Es gibt sogar eine stärkere Version des Pump-Lemmas, in der sich der Teil überall befinden kann (nicht unbedingt am Anfang oder Ende). Die übliche Variante ( , steht neben dem Anfang) ist zweckmäßig.

| y z | < p

$|yz|<p$

y

$y$

| x y | < p

$|xy|<p$

y

$y$

Ran G.

@RanG. Wie ist eine Version, in der die Position von beliebig stärker ist? Ich denke, ich habe erklärt, wie das schwächer wäre. Oder sagt diese Version andere Dinge aus?

y

$y$

Raphael

Es ist stärker, da es Ihnen mehr Flexibilität gibt: Vielleicht steht der Teil, den Sie pumpen möchten, nicht am Anfang des Wortes. In der Tat hat es immer noch ein Äquivalent von weil es nicht "schwächer" ist, wie Sie sagen, aber ohne es am Anfang genau lokalisieren zu müssen. Stellen Sie sich Ogdens Lemma als die allgemeinste Form vor.

| x y | < p

$|xy|<p$

Ran G.

1

@Raphael, zum Beispiel reicht die oben angegebene Version nicht aus, um zu beweisen, dass nicht regelmäßig ist (kann das pumpen ), aber mit überall liegt es ist ganz einfach.

{a b^{n} c^{n} : n \geq 0} \cup a a^{+} b^{*} c^{*}

$\{a b^n c^n \colon n \ge 0\} \cup a a^+ b^* c^*$

a

$a$

y

$y$

vonbrand

@vonbrand: Ich verstehe jetzt, was Ran bedeutet, danke.

Raphael

3

Ich werde nur einige Hinweise zum Pump-Lemma für reguläre Sprachen geben. Die Argumentation ist ähnlich genug für die andere. Stellen Sie sich als den Teil von , der von allem erzeugt wird, bevor Sie die erste Schleife zum ersten Mal starten. als alles, was in dieser bestimmten Schleife für die erste Schleife erzeugt wurde; und als alles, was nach dem ersten Schleifen erzeugt wurde. $x$ $s$ $y$ $z$

Da , und ist die Anzahl der Zustände im minimalen endlichen Automaten (z. B.), die die Sprache akzeptieren, dann muss der Automat eine Schleife durchlaufen haben (da sonst höchstens Übergänge möglich gewesen wären). Daher ist nicht leer; wir stellen die Tatsache fest, dass, da wir eine Zeichenfolge einer bestimmten Länge haben, der Automat, der sie akzeptiert, irgendwann eine Schleife haben muss, so dass gerechtfertigt ist. $|s| \geq p$ $p$ $p-1$ $y$ $|y|>1$
Da das erste Mal ist, dass Sie die erste Schleife durchlaufen, und alles davor ist, haben Sie keinen Zustand im Automaten mehr als einmal besucht. Da gibt esZustände im Automaten, und Sie haben nicht alle besucht, Sie haben . $y$ $x$ $|p|$ $|xy| < p$

Dies sind nicht so viele Hypothesen, die Unterstützung erfordern. Sie sind Tatsachenaussagen, die darauf basieren, wie das Pump-Lemma in Form endlicher Automaten erfunden wurde.

Patrick87
quelle

2

Wenn Sie sich durch die Zustände eines Automaten bewegen, werden Sie schließlich einen Zyklus erreichen. Der Zyklus ist . Es macht keinen Sinn, ein leeres Wort zu pumpen, daher Bedingung 1. ist die Anzahl der Symbole, die Sie lesen mussten, um den ersten Zyklus zu finden. Dies kann unmöglich mehr als die Anzahl der Zustände sein, daher Bedingung 2. Fast per Definition kann ein Zyklus beliebig oft wiederholt werden, daher Bedingung 3. $y$ $xy$

Die kontextfreie Variante ist sehr ähnlich. Die erste Bedingung ist, dass wir nur nach nützlichen Zyklen suchen. Die zweite Bedingung besagt, dass ein Zyklus gefunden werden kann, weil Ihnen die Nicht-Terminals ausgehen. Die dritte Bedingung besagt, dass Sie einen Zyklus, sobald Sie ihn haben, pumpen können. Beachten Sie, dass Sie einen Analysebaum zeichnen sollten, um einen Zyklus im kontextfreien Fall anzuzeigen.

Karolis Juodelė
quelle

2

Es gibt Varianten des Pump-Lemmas. Ich werde deine benutzen.

Beachten Sie, dass Sie wirklich 3 Längenbedingungen haben. Das fehlende ist ungefähr die minimale Gesamtlänge des Wortes. Ich behandle es mit der zweiten Bedingung.

Kurz gesagt:

Ich nenne Teilbaum jeden Teil des Analysebaums, der höchstens ein Nicht-Terminal am Rand hat. Das Pump-Lemma verwendet rekursive Teilbäume, bei denen das Nicht-Terminal im Rand mit der Wurzel des Teilbaums identisch ist. Der gesamte Analysebaum ist ein Teilbaum.

Teilbäume wie hier definiert (und rekursive Teilbäume) sind das Herzstück der Sache. Ihre Existenz steht in direktem Zusammenhang mit der Kontextfreiheit .

1. Bedingung : Es heißt einfach, dass ein unproduktiver (Rand ohne Termina-Symbol) rekursiver Teilbaum im Analysebaum kurzgeschlossen werden kann, sodass wir immer sicher sind, dass der Rand ein Endsymbol enthält.

Ein Endlichkeitsproblem : Es wird zweimal verwendet. Wenn Sie einen Teilbaum haben, der keinen rekursiven Teilbaum enthält, hat kein Pfad im Teilbaum die gleiche Bezeichnung (mit Ausnahme des Teilbaumstamms). Der Teilbaum verzweigt sich endlich mit einer begrenzten Tiefe (nicht mehr als die Anzahl der Nicht-Terminals). Daher haben Sie eine endliche Menge solcher Teilbäume, die nur eine endliche Menge von Zeichenfolgen an ihrem Rand erzeugen. Da die Anzahl begrenzt ist, gibt es eine Obergrenze für die Länge der Ränder. Wenn ein Rand die Grenze überschreitet, ist dies ein sicherer Hinweis darauf, dass er einen rekursiven Teilbaum enthält.

"fehlende Bedingung" : Die "fehlende Bedingung", die sicher, dass die Zeichenfolge lang genug ist, sodass mindestens ein rekursiver Teilbaum im Analysebaum zum Pumpen vorhanden ist. $\mid s\mid \geq p$

2. Bedingung : Sie können immer einen rekursiven Teilbaum pumpen, der weder dominiert noch einen anderen rekursiven Teilbaum im Analysebaum enthält. Wenn dies der Fall ist, nehmen Sie einfach den anderen rekursiven Teilbaum. Da der Analysebaum endlich ist, endet dies. Ende erhalten Sie Teilbäume (für und für ), die keine rekursiven Teilbäume enthalten, und die obige Endlichkeitsanalyse garantiert die Existenz einer Obergrenze. $vy$ $x$

Im normalen Grammatikfall haben Sie nur Teilbäume, die nicht sehr stark verzweigen. Es ist wirklich identisch mit dem CF-Fall, wobei einige Zeichenfolgen durch . $\epsilon$

Im CF-Fall ist es für den Beweis des Lemmas oder seiner Variationen häufig zweckmäßig anzunehmen, dass die Grammatik CNF ist (abhängig auch von der Lemma-Variante).

Ein Großteil des formalen Beweises ist die mathematische Darstellung, nicht das Verständnis.

Dies war eine interessante Übung.

babou
quelle

Woher kommen die Längenbeschränkungen des Pump-Lemmas?

Antworten: