112.07_pumping_lemma.md - scattered-lenity

cards-deck: date-created: 2024-02-21 12:07:36 date-modified: 2024-05-07 01:55:33

;# Pumping - Lemma

part of [[112.00_anchor_overview]]

Motivation

Wir wollen unter Anwendung dieses Prinzips, des Lemmas, zeigen, dass es Sprachen gibt die nichr regulär sind.

Wir wissen, dass man reguläre Sprachen $L$ mit einem Automaten (DFA/NFA/GNFA) und eines regulären Ausdrucks beschreiben kann. Aus dieser Prämisse folgt jetzt:

jede reguläre Sprache, auch die unendlichen, enthalten nur endlich viele Muster –> die Unendlichkeit kommt höchstens von Ausdrücken der Form $[A T] *$ zustande ( weil wir hier beliebige wiederholen dürften)
Eine Sprache die sich nicht durch einen endlichen regulären Ausdruck beschreiben lässt, kann nicht reguläre sein!

Welche Intuition kann man für das Pumpin-Lemma setzen? Worauf zielt es ab? #card
Als Intuition betrachtet, möchten wir gerne sehr lange Wörter in kleinere aufteilen, damit wir sie einfacher und ohne Bedenken des Speicherplatzes bearbeiten und verarbeiten können. Ferner möchten wir somit herausfinden, ob ein Wort Das heißt wir teilen unser großes Problem, in viele kleinere auf. [[111.99_algo_branchNBound#Branch and Bound]]]

Definition - Pumping-Lemma :

Das Lemma kann aufgrund seiner Struktur und der Betrachtung von Wörtern, die größer $n$ sind nur Aussagen über lange Wörter treffen, da wir die Fälle von kleineren Wörtern $\leq n$ nicht ferner betrachten. ( Also solche Wörter, die kleiner als die Menge von Zuständen ist / wäre) Sei $A$ eine reguläre Sprache über das Alphabet $Σ$ . was können wir mit langen Wörtern dieser Sprache machen, welcher Parameter ist dabei wichtig? #card Dann gibt es eine natürliche Zahl $n$ , so dass sich alle Wörter $s \in A$ mit Länge $∣ s ∣ \geq n$ zerlegen lassen in drei Teilworte $s = zy x, x, z, y \in Σ^{*}$ , sodass gilt:

[!Definition] Pumping Lemma | welche drei Attribute gelten unter welcher Annahme? #card Sei $A$ eine reguläre Sprache über $Σ$ . Dann gibt es jetzt ein $n \in N$ , sodass sich alle Worte $s \in A$ mit Länge $∣ s ∣\geq n$ so in drei Teile zerlegen lässt, dass $s = x yz; x, y, z \in Σ^{*}$ sodass dann folgend gilt:

$\forall i \geq 0, z y^{i} z \in A$ –> Es gibt also eine Schleife

$∣ y ∣ > 0$ –> das Wort in der Mitte darf also niemals ein leeres Wort $ϵ$ sein und diese Schleife ist $> 0$ (in ihrer Wiederholung; also mind. einmal)

$∣ x y ∣ \leq n$ –> die Schleife wird spätestens nach $n$ Zustandswechseln erreicht (also $x$ kann beispielsweise alle $n$ Zustände erreichen und danach wird die Schleife erst auftreten)

In dieser Betrachtung ist wichtig, dass die Verbindung :ZYX sich als gesamtes Konstrukt in der Sprache befinden muss, aber die einzelnen Wörter Z,Y,X keine akzeptierten Wörter sein müssen.

[!attention] Folgerung “Unendlich lange Programm von endlichen Automaten müssen immer Schleifen aufweisen -> bzw innerhalb eines Wortes einer Sprache kann man unter Umständen einen Term finden, welcher sich $i$ mal wiederholt.

Wenn man etwa 2 unterschiedlich Schleifen konzipiert, gilt dieses Lemma dennoch, weil sich diese Schleifen auf obiger Betrachtung auch wiederholen und wir somit eine große, übergeordnete Schleife haben/ betrachten

[!tip] Bemerkungen zum Pumping Lemma Bedeutung für endlichen Sprachen?, kann es Regularität zeigen? #card Für endliche Sprachen ist die Anwendung des Pumping Lemmas trivial, denn $n$ wird dann die maximale Wortlänge sein ( denn wenn es schleifen gibt, muss man diese beliebig wiederholen können ( der Automat kann es ja nicht zählen!))

Das Lemma ist nur ein notwendiges Kriterium für die Regularität: Man kann es also nicht verwendet, um die Regularität zu beweisen –> nur die Nicht-Regularität!

Anwendung Pumping Lemma

[!Important] Nutzung des Pumping-Lemmas

wofür können wir das Pumping Lemma nutzen? #card

Das Pumping-Lemma kann nur genutzt werden, um zu zeigen, dass eine Sprache nicht regulär ist.

Dafür möchten wir die formale Betrachtung des Lemmas anschauen und es anschließend an einem Beispiel anwenden:

Mathematische Repräsentation

[!Definition] Pumping-Lemma formal was sagt das Pumping lemma formal aus? Wie sieht weiterhin die Kontraposition aus? #card

Formal meint das Pumping-Lemma: $(A ⟹ B)$ $A \in REG ⟹ (\exists n \in N, \forall s \in A :∣ s ∣> n \exists x, y, z; ∣ y ∣> 0, ∣ x y ∣\leq n; \forall i \in N : x y^{i} z \in A)$ (Also wir können eine Schleife finden, die eine bestimmte Länge übersteigt, sodass man dann eine Wort in der Sprache aufteilen kann in (Anfang| Schleifenpart | Ende)) Und als Kontraposition folgt: $(\neg B ⟹ \neg A)$ ( gibt es ein Wort, was man entsprechend aufteilen kann, was nicht in der Sprache liegt, dann ist sie nicht regulär!) $(\forall n \in N \exists s \in A :∣ s ∣> n; \forall x, y, z; ∣ y ∣> 0; ∣ x y ∣\leq n, \exists i \in N : x y^{i} z \neq \in A) ⟹ A \neq \in REG$

[!Attention] Zeigen, dass Sprache nicht regulär ist, brauch also die linke Seite der Kontraposition!

mathematische Betrachtung :

Sei A regulär $⟹$ $\exists n \in N \forall S mit ∣ s ∣ \geq n, s \in L \exists x, y, z \in Σ^{*} mit ∣ y ∣ > 0, ∣ x y ∣ \leq n \land \forall i \in N_{0} : x y^{i} z \in A$ wie sieht die Kontraposition aus? #card Unter Anwendung können wir die Kontraposition betrachten, also : $\neg (\exists n \dots) ⟹ A$ nicht regulär $⟺ \forall n \exists s \forall x, y, z \in Σ^{*} \exists i : x y^{i} z \neq \in A$

Beweisidee : - Pumping Lemma

Grundlegend möchten wir zeigen, dass diese Schleife immer dann auftritt, wenn ein DFA/NFA eine unendliche Sprache erkennen kann - anderweitig ist es keine reguläre Sprache.

Sofern $M$ ein Automat ist, der die Sprache $A$ erkennt, wählen wir $n$ als die Anzahl der Zustände die $M$ haben kann. Also wir decken später so ab, dass alle Wörter, die am Ende größer sein werden, als die Menge von Zuständen die wir haben, auch zerteilt werden können, damit wir sie in kleineren Strukturen betrachten und Verarbeiten können. Was muss ferner betrachtet werden, was ist bei Wörtern wichtig. Was passiert, wenn der Automat n+1 von n maximalen Zuständen durchläuft? #card Wir betrachten nun die Verarbeitung eines Wortes $w$ der Länge $> n$ Der Automat besucht dabei also $n + 1$ Zustände – inklusives des Starts. Da der Automat nur $n$ Zustände aufweist, muss es einen Zustand im Verlauf des großen Wortes geben, welcher mindestens zweimal besucht wird: Das weißt daraufhin, das es eine Schleife geben muss! Anderweitig ist diese Konzeption nicht umsetzbar.

stateDiagram-v2
[*]-->q0
q0-->qi:von 1 bis w, ist =
qi-->qi: von w bis rj, ist y
qi-->qEnd:von rj bis End, ist z

[!Important] Notwendigkeit des Schubfachprinzips **Wir haben hier also das Pigeon-Hole Principle (Schubfachprinzip) angewandt, um zu zeigen, dass es eine Schleife geben muss!

Wir haben hier also eine mögliche Schleife im Automat. Und da sie sich innerhalb des ganzen Wortes befinden wird, können wir sie auch beliebig oft durchlaufen! –> Schließlich ist der Anfang mit x gegeben, und das Ende mit $y$ ebenfalls -> die Teile, die nicht von der Schleife - egal wie groß oder tiefgreifend sie ist - eingeschlossen werden!

Sofern man beispielsweise das Wort in $4 - 5$ Worte zerteilen kann, also etwa 2 verschiedene Schleifen betrachtet, dann werden wird dieser Bweis nicht ausschließen, dass diese Struktur machbar ist, aber was es auch besagt, dass es eine Wiederholung zwischen bestimmten Zuständen geben muss, sodass ein Zustand mindestens 2 mal besucht wird. Ferner folgert es dann bzw. schließt es auch ein, dass diese zwei unabhängigen Schleifen auftreten, weil wir dennoch gemäß des Schubfachprinzipes garantiert auf diese treffen müssen!

[!Important] Länge von $x$ Die Länge von $x$ muss höchstens N Zustände haben, :: damit wir anschließend abschließen können, dass eine Wiederholung auftreten muss -> weil man dann erkennen wird / soll, dass sich bei Wörtern $> n$ halt Wiederholungen notwendig sind

formaler Beweis:

Unter der Vorbetrachtung eines solchen Automaten, können wir den Beweis ähnlich strukturiert durchführen.

Sei $M$ ein deterministischer Automat, der $A$ erkennen kann. Wir setzen $n$ gleich der Anzahl von Zuständen. Sei weiterhin $w = s_{1} \dots s_{m}$ ein String der Länge $m > n$ . Sei $r_{0}, \dots, r_{m}$ die Folge der Zustände die der Automat bei der Verarbeitung von $w$ durchläuft. Unter den ersten $n + 1$ dieser Zustande muss es mindestens einen geben, der? Und warum tritt dieser Zustand ein? Was können wir aus diesen im Bezug auf unser Wort folgern? #card Es muss hier mindestens einen geben, der mindestens zweimal vorkommt. (Gemäß des Schubfachprinzipes!). Wir nennen diesen Punkt jetzt ferner $r_{j}, r_{j}$ und grenzen damit den Anfang und das Ende dessen vom Rest ab. Die Abfolge/ Berechnung von Zuständen können wir jetzt entsprechend aufteilen: $r_{0} \to r_{1} \to r_{2} \to \dots \to r_{i - 1} \to r_{i} x \to \dots \to r_{j - 1} \to r_{j} y \to \dots \to r_{n} z$ und somit haben wir jetzt eine Aufteilung vorgenommen, wie sie gefordert wird. Wir setzen demnach: $x y z = s_{1} \dots s_{i} = s_{i + 1} \dots s_{j} = s_{j + 1} \dots s_{m}$ und damit haben wir unsere Aussage bewiesen!

Diese Wahl erfüllt das Pumping-Lemma. Insbesondere fürt ein Wort $x y^{i} z$ immer auch zum Endzustand, wird also akzeptiert. weswegen wird dieses Wort dann immer akzeptiert? #card

Das kommt daher, dass die Beliebige Replikation von Y, $i -$ mal ausgeführt werden kann.

Anwendungsbeispiel : nicht reguläre Sprachen

Stehe die Behauptung: Die Sprache L = ${0^{n} 1^{n} ∣ n \in N}$ ist nicht regulär. Diese Behauptung könne man dann mit dem Pumping-Lemma beweisen. Was wäre ein mögliches Vorgehen? #card Beweis dafür, mit Hilfe des Pumping-Lemmas: $L = {0^{n} 1^{n} ∣ n \in N}$ –> das heißt die Menge von 0 und 1 ist immer gleich und somit entstehen folgende Worte: ${0011, 01, 000111, \dots}$ . Wir wählen nun ein beliebiges $\forall n e \in N$ ( es wird für alle gelten!). Weiter wählen wir ein Wort $s = 0^{n} 1^{n} : ∣ s ∣= 2 n > n$ (logisch, da wir das durch die Bildungsvorschrift fordern.) Sei nun $s = x yz$ eine beliebige Zerlegung des Wortes mit $∣ y ∣ > 0, ∣ x y ∣\leq n$ ( also die geforderte Zerlegung für das Pumping-Lemma) Es muss jetzt die Schleife gefunden werden: $\exists i \in N : x y^{i} z \neq \in L$ (wir möchten es finden.) Wir wissen, dass $∣ x y ∣ \leq n$ und somit wird $y = 0 \dots$ sein ( wir geben ja an, dass es $n$ 0 und $n$ 1) gibt! Es folgt somit: $x 0 \dots 0 0 \dots 0 y 0 \dots 1 \dots 1 z$ . exemplarisch ist $x y^{2} z \neq \in L$ , da es dann mehr 0 als 1 haben wird!

Wir können diesen Umstand auch verallgemeinern und mit drei Zuständen betrachten:

Fall 1 : y besteht nur aus 0en: $s = 0000001111$ Dann ist $x y^{2} z \neq \in L$ da es mehr 0er als 1er gibt.
Fall 2 : y nur aus 1en, analog.
Fall 3 : y hat 0en und 1en: s= 0000 1111 Dann ist aber $x y^{2} z \neq \in L$

[!Attention] Trick / Hilfreicher Tipp bei der Beantwortung eines Beweis Betrachten wir hier die Bildungsvorschrift für das Pumping-lemma - negiert - und versuchen dafür jetzt entsprechend die Quantoren durchzuarbeiten. Wir werden relativ früh ein $\exists \in A : ∣ s ∣> n$ betrachten. Hierbei können wir also genau ein Beispiel finden und müssen so nicht immens allgemein argumentieren. Im Beispiel nutzten wir etwa: $∣ s ∣= 2 n > n$ !

[!Tip] weitere Sprache: Betrachte eine weitere Sprache: $l = {w ∣ Teislstring 01,10 tauchen gleich oft auf}$ ist die Sprache regulär? #card Nein, man kann hier einen Loop bilden