Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Pumping Lemma - Automaten & Formale Sprachen 12
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 77 Zeilen
- Ey Lemma! Schon wieder hart am pumpen oder was ?
- Läuft bei dir Oida! Da machen wir doch gleich mit und legen auch los!
- Also, was ist jetzt das Pumping Lemma? Hat natürlich nix mit Sport zu tun.
- Mit dem Pumping Lemma kann man grob gesagt einfach zeigen,dass eine Sprache nicht regulär ist.
- 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
- uns erstmal nicht. Bevor uns das Pumping Lemma jetzt genauer anschauen, betrachten wir mal folgenden NEA.
- 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.
- Zuerst sind wir im Anfangszustand q0, dann q1
- dann q2 dann q3
- und dann nochmal q1 Das ist der Weg, in dem ein Wort mit 4 Zeichen erkannt wird.
- Der Knoten q1 wird somit doppelt abgegangen. Da der Knoten doppelt abgegangen wurde, muss es also einen Zyklus in dem Pfad geben.
- 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
- das Wort erkannt wird. Ein Wort kann somit also immer länger werden, wird aber von der Sprache immer noch erkannt.
- 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
- 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.
- Die habt ihr ja bestimmt in der Schule oder im Studium vorgegeben. Wir versuchen jetzt zu verstehen, was das Pumping Lemma genau beschreibt.
- Das Pumping Lemma besagt, dass für jede reguläre Sprache eine natürliche Zahl , die Anzahl der Zustände, existiert.
- 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
- x,y und z möglich ist. X ist dabei das Wort vor dem Zyklus.
- Bei uns im Beispiel vorhin also das Wort bzw. Zeichen von q0 nach q1. Y ist der Zyklus, bzw. das Wort im Zyklus.
- 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.
- Z ist das Wort, was nach dem Zyklus kommt. Im Beispiel kommt bei uns nix mehr, da wir ja dann im Endzustand sind.
- Beim Pumping Lemma gilt außerdem, dass dieses Y , also der Zyklus , beliebig oft wiederholt oder aufgepumpt werden kann.
- Daher auch pumping Lemma, verstehste? Euer Opa sagt jetzt bestimmt so : Whaaaaaaaat?
- 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.
- 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.
- Dabei muss die Länge des Wortes aber mindestens so lang sein wie die Anzahl an Zuständen im Automaten der Sprache.
- Also ganz grob gesagt, natürlich ohne die genauen Definitionen, besagt das Pumping Lemma genau das!
- Aber damit man jetzt auch die wirkliche Anwendung sieht, schauen wir uns das ganze an nem Beispiel an.
- Das einfachste Beispiel zum Pumping Lemma ist a hoch n, b hoch n . N ist dabei eine natürliche Zahl.
- Wir wissen schon von der Sprache, dass sie nicht regulär ist. Das gilt es jetzt zu beweisen.
- Wir suchen also ein Wort a hoch n , b hoch n , welches in der Sprache liegt und bei dem das Pumping Lemma fehlschlägt.
- 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.
- Natürlich sollte es auch mit anderen Zahlen aufgepumpt werden können, aber des is jetzt am einfachsten.
- Oke, also zum ersten Fall. Unser Teilwort könnte jetzt sowohl as als auch bs enthalten.
- 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.
- 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
- noch ein b enthält. Unsere Sprache besteht ja immer aus a hoch n , b hoch n.
- 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.
- Wir hätten also aabbaabb. Auch wenn wir jetzt x und z nicht betrachten, sehen wir sofort, dass dieses Teilwort y nicht
- mehr in der Sprache liegt. Die Form entspricht ja nicht mehr a hoch n , b hoch n.
- Somit stimmt der erste Fall schonmal nicht. Klaro oder? Dann zum zweiten Fall.
- Unser Teilwort y kann natürlich auch nur as enthalten. Also zum Beispiel aa.
- 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
- werden. Was stimmt jetzt hier nicht?
- Richtig. Das Wort wäre jetzt nicht mehr in der Form a hoch n , b hoch n. Somit geht dieser Fall auch nicht klar.
- Der letzte Fall ist jetzt, dass unser y nur aus bs besteht. Zum Beispiel sowas wie bb.
- 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.
- Jetzt ist das genau das gleiche wie vorher beim a. Das Wort erfüllt nicht mehr die Sprache a hoch n, b hoch n.
- 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!
- 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
- Fälle ab, damit wir safe sind! Eigentlich ganz logisch wa?
- Natürlich kann es sein, dass ihr in der Uni oder Schule schwerere Beispiele bekommt. Der Ablauf ist aber immer gleich.
- Ihr geht alle Fälle für y durch und überprüft dabei ob die Zerlegung und das aufpumpen möglich ist.
- So wie so oft läuft es in der Uni ein bisschen anders. Da müsst ihr meistens das Pumping Lemma allgemeiner beweisen.
- 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.
- 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
- 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.
- 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
- besteht. Es enthält also eine bestimmte Anzahl an a`s. Für y sagen wir, dass y = a hoch j ist.
- 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
- 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.
- 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.
- Das heißt, dass aus unserem Wort xyz ein xyyz wird. Jetzt schreiben wir die vorher definierten Werte auf.
- 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
- 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.
- 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.
- 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
- in der Uni begegnen. Was merkt ihr euch jetzt?
- 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.
- 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
- folgendes. Es muss möglich sein ein Wort in drei Teilwörter x,y und z zu zerlegen.
- X ist ein Teilwort vor dem Zyklus. Y ist der Zyklus selbst.
- Dieses Teilwort darf nicht leer sein und muss beliebig oft aufgepumpt werden können. Z ist ein Teilwort nach dem Zyklus.
- In der Praxis geht ihr alle Möglichkeiten für y durch und überprüft ob es möglich ist, dieses y aufpumpen.
- 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!
- Tschööööööö!
Zum Nachlesen
AutomatentheorieDie Automatentheorie ist ein Teilgebiet der theoretischen Informatik, das sich mit dem Studium von Automaten (Modellrechnern) und mit den von diesen …
Theoretische InformatikIhre Inhalte sind die Automatentheorie, die Theorie der formalen Sprachen, die Berechenbarkeits- und Komplexitätstheorie, aber auch die Logik und formale …