Pumping Lemma - Automaten & Formale Sprachen 12
Informatik - simpleclub
https://www.youtube.com/watch?v=TZOeXLWVer4

Transkript (automatisch erstellt)

0:00 Ey Lemma! Schon wieder hart am pumpen oder was ?
0:02 Läuft bei dir Oida! Da machen wir doch gleich mit und legen auch los!
0:06 Also, was ist jetzt das Pumping Lemma? Hat natürlich nix mit Sport zu tun.
0:14 Mit dem Pumping Lemma kann man grob gesagt einfach zeigen,dass eine Sprache nicht regulär ist.
0:20 Allerdings kann man nicht zeigen, dass sie regulär ist. Was regulär genau bedeutet, schauen wir uns aber in nem anderen Video genau an und interessiert
0:27 uns erstmal nicht. Bevor uns das Pumping Lemma jetzt genauer anschauen, betrachten wir mal folgenden NEA.
0:32 Der NEA erkennt jetzt zum Beispiel ein Wort der Länge 4. Da die Länge 4 ist, müssen wir insgesamt 4 Kanten und somit 5 Knoten abgehen.
0:41 Zuerst sind wir im Anfangszustand q0, dann q1
0:45 dann q2 dann q3
0:49 und dann nochmal q1 Das ist der Weg, in dem ein Wort mit 4 Zeichen erkannt wird.
0:54 Der Knoten q1 wird somit doppelt abgegangen. Da der Knoten doppelt abgegangen wurde, muss es also einen Zyklus in dem Pfad geben.
1:00 Das wäre jetzt der Weg von q1 über q2 und q3 zurück nach q1. Diesen Zyklus können wir also beliebig oft gehen und gleichzeitig sicherstellen, dass
1:09 das Wort erkannt wird. Ein Wort kann somit also immer länger werden, wird aber von der Sprache immer noch erkannt.
1:15 Wenn man das Verstanden hat, versteht man auch das Pumping Lemma. Das basiert nämlich auf dieser Vorgehensweise, nur dass die Definition vom Pumping Lemma
1:23 für jeden Automaten anwendbar ist und nicht nur für unser Beispiel. Die förmliche Definition vom Pumping Lemma ersparen wir euch jetzt mal.
1:33 Die habt ihr ja bestimmt in der Schule oder im Studium vorgegeben. Wir versuchen jetzt zu verstehen, was das Pumping Lemma genau beschreibt.
1:42 Das Pumping Lemma besagt, dass für jede reguläre Sprache eine natürliche Zahl , die Anzahl der Zustände, existiert.
1:48 Für alle Wörter die in der Sprache liegen muss dann gelten, dass falls die Wortlänge größer oder gleich der Anzahl der Zustände ist,eine Zerlegung des Wortes in drei Teilwörter
1:57 x,y und z möglich ist. X ist dabei das Wort vor dem Zyklus.
2:02 Bei uns im Beispiel vorhin also das Wort bzw. Zeichen von q0 nach q1. Y ist der Zyklus, bzw. das Wort im Zyklus.
2:11 Das wäre bei uns das Wort zwischen q1,q2,q3 und zurück zu q1. Y muss immer existieren, darf also nicht leer sein.
2:19 Z ist das Wort, was nach dem Zyklus kommt. Im Beispiel kommt bei uns nix mehr, da wir ja dann im Endzustand sind.
2:25 Beim Pumping Lemma gilt außerdem, dass dieses Y , also der Zyklus , beliebig oft wiederholt oder aufgepumpt werden kann.
2:31 Daher auch pumping Lemma, verstehste? Euer Opa sagt jetzt bestimmt so : Whaaaaaaaat?
2:44 Also …. durch das Pumping Lemma versuchen wir zu beweisen, dass eine Sprache nicht regulär. Wir versuchen also ein Wort zu finden, was die Definition vom Pumping Lemma nicht erfüllt.
2:54 Dabei muss es möglich sein ein Wort in drei Teilwörter x,y und z zu zerlegen und den Zyklus y beliebig oft wiederholen bzw. aufpumpen zu können.
3:04 Dabei muss die Länge des Wortes aber mindestens so lang sein wie die Anzahl an Zuständen im Automaten der Sprache.
3:09 Also ganz grob gesagt, natürlich ohne die genauen Definitionen, besagt das Pumping Lemma genau das!
3:15 Aber damit man jetzt auch die wirkliche Anwendung sieht, schauen wir uns das ganze an nem Beispiel an.
3:21 Das einfachste Beispiel zum Pumping Lemma ist a hoch n, b hoch n . N ist dabei eine natürliche Zahl.
3:26 Wir wissen schon von der Sprache, dass sie nicht regulär ist. Das gilt es jetzt zu beweisen.
3:31 Wir suchen also ein Wort a hoch n , b hoch n , welches in der Sprache liegt und bei dem das Pumping Lemma fehlschlägt.
3:38 So, jetzt müssen wir uns erstmal überlegen welche Wörter unser x,y und z enthält. Zuerst sagen wir mal, dass unser y mit hoch 2 aufgepumpt wird.
3:47 Natürlich sollte es auch mit anderen Zahlen aufgepumpt werden können, aber des is jetzt am einfachsten.
3:52 Oke, also zum ersten Fall. Unser Teilwort könnte jetzt sowohl as als auch bs enthalten.
3:58 Dabei is jetzt egal wie viele as und wie viele bs enthalten sind. Es ist nur wichtig, dass sowohl as, als auch bs in y sind.
4:05 Was passiert jetzt wenn y zum Beispiel aabb ist? Vor dem y stehen ja als x jetzt entweder ein leeres Wort, oder aber nur as, da das y ja
4:15 noch ein b enthält. Unsere Sprache besteht ja immer aus a hoch n , b hoch n.
4:20 Somit ist besteht unser z dann aus einem leeren Wort oder aber nur aus bs. Wenn wir das y jetzt mit 2 aufpumpen, würde sich unser Teilwort aabb ja wiederholen.
4:30 Wir hätten also aabbaabb. Auch wenn wir jetzt x und z nicht betrachten, sehen wir sofort, dass dieses Teilwort y nicht
4:38 mehr in der Sprache liegt. Die Form entspricht ja nicht mehr a hoch n , b hoch n.
4:44 Somit stimmt der erste Fall schonmal nicht. Klaro oder? Dann zum zweiten Fall.
4:49 Unser Teilwort y kann natürlich auch nur as enthalten. Also zum Beispiel aa.
4:53 Jetzt wird wieder mit 2 aufgepumpt und wir kriegen für y ein aaaa. Wenn das ganze Wort jetzt also ein aaabbb wäre, dann würde das durch das y ja zu aaaaabbb
5:06 werden. Was stimmt jetzt hier nicht?
5:08 Richtig. Das Wort wäre jetzt nicht mehr in der Form a hoch n , b hoch n. Somit geht dieser Fall auch nicht klar.
5:15 Der letzte Fall ist jetzt, dass unser y nur aus bs besteht. Zum Beispiel sowas wie bb.
5:20 Wenn wir das jetzt wieder aufpumpen mit 2, kriegen wir für y ein bbbb. Gehen wir wieder vom Wort aaabbb aus, kriegen wir also aaabbbbb raus.
5:32 Jetzt ist das genau das gleiche wie vorher beim a. Das Wort erfüllt nicht mehr die Sprache a hoch n, b hoch n.
5:39 Da unser y ja nicht leer sein kann, haben wir alle Fälle abgearbeitet. Da es in keinem Fall möglich ist unser y aufzupumpen, ist die Sprache somit nicht regulär!
5:48 Es reicht jetzt nicht,nur ein Wort zu finden, was nicht in der Sprache liegt. Von diesem müssten wir wieder alle Zerlegungen betrachten, also gehen wir lieber gleich alle
5:56 Fälle ab, damit wir safe sind! Eigentlich ganz logisch wa?
6:00 Natürlich kann es sein, dass ihr in der Uni oder Schule schwerere Beispiele bekommt. Der Ablauf ist aber immer gleich.
6:05 Ihr geht alle Fälle für y durch und überprüft dabei ob die Zerlegung und das aufpumpen möglich ist.
6:12 So wie so oft läuft es in der Uni ein bisschen anders. Da müsst ihr meistens das Pumping Lemma allgemeiner beweisen.
6:17 Betrachten wir nochmal das Beispiel von oben. Wir nehmen uns erstmal ein allgemeines Wort w raus, dass in der Sprache liegt. Also zum Beispiel a hoch m b hoch m.
6:26 Dann müssen wir noch ganz plump hinschreiben, dass unsere Definition gilt. W liegt also in der Sprache L und es gilt schonmal, dass die Länge von w größer gleich
6:35 m ist. Somit gilt dann auch, dass man w in die Teilwörter zerlegen kann,y nicht leer ist und die Länge von xy kleiner gleich m ist.
6:43 So, jetzt haben wir schon mal die Definition abgeschrieben. Jetzt gehen wir die Teilwörter an. Erstmal sagen wir, dass des x aus a hoch i
6:51 besteht. Es enthält also eine bestimmte Anzahl an a`s. Für y sagen wir, dass y = a hoch j ist.
6:57 Also wieder eine bestimmte Anzahl an a´s. So was bleibt jetzt für z? Da x und y schon eine bestimmte Anzahl an a´s belegen, bleibt für z nur noch der Rest
7:06 der von den a´s übrig ist. Somit besteht z schonmal aus a hoch m-i-j. Die Anzahl die x und y schon beanspruchen, müssen ja von der Gesamtzahl abgezogen werden.
7:18 Klar soweit? Jetzt enthält das Teilwort z ja auch noch b hoch m , da x und y ja keine b´s enthalten. Was passiert wenn wir jetzt y mit zwei aufpumpen.
7:28 Das heißt, dass aus unserem Wort xyz ein xyyz wird. Jetzt schreiben wir die vorher definierten Werte auf.
7:36 Dann schreiben wir die Potenzen bei a zusammen. Das wird jetzt zusammengefasst. So, wat heißt das jetzt? Unser a kommt somit häufiger vor als unser
7:45 b , da wir zur Anzahl von a ja noch ein j addieren. Somit kann a auf jeden Fall häufiger vorkommen, wenn j zum Beispiel 4 oder so ist.
7:53 Dann liegt dieses Wort aber nicht mehr in a^n b^n. Somit schlägt das Pumping Lemma fehl und die Sprache ist nicht regulär.
8:00 Bam Oida! Somit haben wir jetzt ganz allgemein gezeigt, dass die Sprache nicht regulär ist. So ein Vorgehen wird euch so gut wie immer
8:07 in der Uni begegnen. Was merkt ihr euch jetzt?
8:10 Durch das Pumping Lemma versuchen wir zu beweisen, dass eine Sprache nicht regulär. Wir können damit aber nicht beweisen, dass sie Regulär ist.
8:16 Das Pumping Lemma besagt, dass eine Natürliche Zahl, die Anzahl an Zuständen, existiert. Für alle Wörter in der Sprache mit Länge größer oder gleich dieser Zahl gilt dann
8:26 folgendes. Es muss möglich sein ein Wort in drei Teilwörter x,y und z zu zerlegen.
8:30 X ist ein Teilwort vor dem Zyklus. Y ist der Zyklus selbst.
8:34 Dieses Teilwort darf nicht leer sein und muss beliebig oft aufgepumpt werden können. Z ist ein Teilwort nach dem Zyklus.
8:42 In der Praxis geht ihr alle Möglichkeiten für y durch und überprüft ob es möglich ist, dieses y aufpumpen.
8:53 Falls das nicht für jeden Fall möglich ist, ist die Sprache nicht Regulär. So dat wars jetzt zu dem Pumping Lemma. Wir sehen uns dann im nächsten Video!
9:10 Tschööööööö!