Das pumpende Lemma für reguläre Sprachen ist ein leistungsstarkes Instrument, um zu beweisen, dass eine Sprache * nicht * regelmäßig ist. Es funktioniert im Widerspruch:Sie gehen davon aus, dass die Sprache * regelmäßig ist, und dann zeigen, dass diese Annahme zu einem Widerspruch des Lemma selbst führt. So funktioniert es:

1. Die pumpende Lemma -Anweisung:

Das pumpende Lemma stellt fest, dass für jede reguläre Sprache L eine Pumplänge P vorhanden ist, so dass jede Saite in l mit Länge | W | ≥ P kann in drei Substrings unterteilt werden, w =xyz, was die folgenden Bedingungen erfüllt:

* | xy | ≤ p: Die Länge der Verkettung von x und y ist geringer als oder gleich p.

* | y |> 0: Das Substring y ist nicht leer.

* für alles i ≥ 0, xy ⁱ z ∈ L: Pumpen y Null oder mehr Male (einschließlich des Entfernens vollständig, wenn i =0) führt zu einer Zeichenfolge, die sich noch in der Sprache L.

2. Beweisstrategie:

Um zu beweisen, dass eine Sprache L nicht regelmäßig mit dem Pumping Lemma verwendet wird, befolgen Sie diese Schritte:

* Angenommen, l ist regelmäßig: Beginnen Sie mit der Annahme, dass L eine reguläre Sprache ist.

* Wählen Sie eine Pumplänge P: Das pumpende Lemma garantiert die Existenz einer Pumplänge p; Sie müssen seinen tatsächlichen Wert nicht finden, und bezeichnen Sie ihn einfach als "P".

* Wählen Sie eine Zeichenfolge w ∈ L, so dass | w | ≥ P: Wählen Sie sorgfältig eine Zeichenfolge W aus der Sprache L, deren Länge mindestens p ist. Die Wahl von W ist entscheidend; Es muss Ihnen ermöglichen, im nächsten Schritt einen Widerspruch zu schaffen. Dies beinhaltet häufig Zeichenfolgen mit einer bestimmten Struktur, die sich auf die Definition der Sprache bezieht.

* Zeigen Sie, dass keine Zersetzung W =xyz die pumpenden Lemma -Bedingungen erfüllt: Dies ist das Herz des Beweises. Für * jede * mögliche Zerlegung von W in xyz befriedigend | xy | ≤ p und | y |> 0, Sie müssen zeigen, dass es einige i ≥ 0 gibt, so dass xy ⁱ Z ∉ L. Dies bedeutet, dass das Pumpen y die Definition der Sprache L verletzt. Oft zeigen Sie dies, indem Sie zeigen, dass das Pumpen y entweder:

* Einlebnis ein Ungleichgewicht vorstellen: Ändern Sie die Anzahl der Vorkommen eines Symbols und verletzen eine Zählbeschränkung in L.

* Erstellen Sie eine ungültige Struktur: Brechen Sie das Muster oder die Struktur durch Ls Definition.

* Ein ungültiges Substring einführen: Erstellen Sie ein Substring, das nicht zur Sprache gehört.

* Schluss, dass L nicht regelmäßig ist: Da Sie gezeigt haben, dass für die gewählte Schnur w keine solche Zersetzung existieren kann, widerspricht dies dem pumpenden Lemma. Daher muss die anfängliche Annahme, dass L regelmäßig ist, falsch sein und L nicht regelmäßig ist.

Beispiel:Beweisen Sie {a ⁿ b n | n ≥ 0} ist nicht regelmäßig:

Sei l ={a ⁿ b n | n ≥ 0}.

1. Angenommen, l ist regelmäßig.

2. Wählen Sie P: Sei P die Pumplänge.

3. Wählen Sie W: Sei w =a ^p b p . Klar, w ∈ L und | W | ≥ p.

4. Betrachten wir eine Zersetzung w =xyz so, dass | xy | ≤ p und | y |> 0. Da | xy | ≤ p, y muss * nur * von a bestehen (weil y ein Substring von den ersten p -Zeichen ist). Daher ist y =a ^k Für einige k> 0. Jetzt pumpen Sie y null mal:xy ⁰ z =a ^p-k b p . Diese Zeichenfolge ist nicht in L, da die Anzahl der A und B von A unterschiedlich ist. Dies widerspricht dem pumpenden Lemma.

5. Schluss: Da wir einen Widerspruch erreicht haben, muss unsere Annahme, dass L regelmäßig ist, falsch sein. Daher ist L ={a ⁿ b n | n ≥ 0} ist keine reguläre Sprache.

Der Schlüssel besteht darin, die String `w` sorgfältig auszuwählen und alle möglichen Zerlegungen` xyz` geschickt zu analysieren, um zu zeigen, dass das Pumpen von `y` immer zu einer Zeichenfolge außerhalb der Sprache führt. Je komplexer die Sprache ist, desto komplizierter wird die Wahl von "W" und die Analyse.