Pumping Lemma für erkennbare Sprachen [IMPROVED]
Вставка
- Опубліковано 4 лип 2018
- Wir sehen uns das Pumping Lemma für erkennbare (bzw. reguläre) Sprachen an. Es beschreibt eine Eigenschaft, die alle erkennbaren Sprachen haben. Wenn eine Sprache diese Eigenschaft nicht hat, kann sich nicht erkennbar sein.
Hallo Leitfaktor, ich möchte dir einfach meinen Dank aussprechen. Viele deiner Videos haben mir die zuerst unattraktiv wirkende theoretische Informatik echt schmackhaft und interessiert gemacht. Ich habe jetzt eine ganz souveräne 1.3 in der Klausur geschrieben und bin absolut stolz. Ich habe den Kanal vielen meiner Kommilitonen empfohlen und wir haben alle davon profitiert. Vielen Dank dafür !
Vielen Dank, es freut mich sehr das zu hören! :)
Was für eine Klausur war das? An welcher Uni bist du? Ich schreibe bald auch meine Klausur. Hattest du neben den Vorlesungsfolien und diesen Videos noch andere gute Quellen?
Würde mich auch interessieren was du sonst als quelle für Übungen etc genommen hast
Hallo Leute, ich beantworte jetzt einfach mal eure beiden Fragen in einem Text.
Die Klausur war theoretische Informatik an der Fachhochschule in Wolfenbüttel (ich studiere Informatik). Als Ausgangspunkt hatten wir ein selbst erstelltes Skript von Herrn Prof. Dr. Seutter. Ein sehr kompetenter Prof, allerdings hat sich der gute Herr in seinem Skript etwas im Formalismus verloren. Ich habe dann auf UA-cam die Videos von Christian Spannagel und Leitfaktor gesehen, um erst einmal die Weichen zu stellen. Dann bin ich auf diese Seite gestoßen : www.inf.fh-flensburg.de/lang/theor/index.htm und habe dort nochmal einen anderen Blick auf die Thematik bekommen. Zu dem Zeitpunkt war ich dann auch thematisch schon so auf Höhe, um das eigene Skript zu verstehen und das Wissen endgültig zu festigen. Nebenbei habe ich, wie auch in anderen Fächern, die Probeklausuren von der Fernuni Hagen in einigen Fächern gemacht. Das gibt wiederum einen anderen Blick aufs Thema.
Letztendlich muss ich hier aber auch jede Illusion wegwischen, dass das Ganze nur durch UA-cam kam. Ich habe alles andere nach hinten geschoben und wirklich 8 Wochen vor der Klausurphase jeden Tag gelernt, gerechnet und geflucht.
Ich hoffe ich konnte euch etwas helfen!
Theoretische Informatik - Kurzgefasst von Uwe Schöning ist auch ganz nett wenn man sich ein tieferes Verständnis möchte
Kann mich den anderen nur anschließen. Du erklärst echt besser als so mancher Dozent und hast mich gut durch die Klausur gebracht. Danke!
Kein Wort zu viel und extrem gut erklärt. Vielen Dank dafür.
Keine Ahnung, ob du so alte Videos noch verfolgst, aber vielen Dank. Das ist sehr gut erklärt. Optisch, semantisch und logisch. Ich hab das Pumping Lemma endlich mal verstanden.
Eins der besten Erklärvideos, die ich je gesehen hab.
DANKE! Habe auf Grund meiner Vorlesungsunterlagen nicht einmal geahnt, was hier erklärt/gezeigt werden soll.
Dank deines Videos ist es super klar!
Du rettest mit deinen Videos einen ganzen Studiengang! Danke :)
Sehr gut erklärt! Die Stimme ist auch sehr angenehm und es macht freunde, zu zuhören.
Wahnsinnig gut erklärt
Das erste Video bei dem ich es verstehe! Danke dir!!! :)
Das Pumping-Lemma ist doch nicht so kompliziert und abstrakt, wie es in den Vorlesungsfolien dargestellt wird :D hatte irgendwie immer mehr Respekt davor als nötig. Vielen, vielen Dank für deine Mühe und Arbeit, uns das so anschaulich zu erklären! Du leistest mit deinem Kanal einen wahnsinnig tollen Job! :3
Vielen Dank für das Lob! :)
Super toll erklärt! Vielen vielen DANK!
Das Video ist richtig stark!!! Vielen lieben Dank.
Du machst richtig gute Arbeit!
Super erklärt! Vielen Dank!)
Informatik Klausur an der Uni bestanden. Danke!
Herzlichen Glückwunsch! Und Danke! :)
Danke für die Erklärung! Seeeehr hilfreich!
Danke für dieses Video❤️
richtig richtig stark erklärt vielen dank!!
sehr gut erklärt, danke
Vielen Dank für die tolle Erklärung. Ich habe nur eine kleine Frage. Wie kann es sein, dass y^i mit i=0 im Pumping Lemma erlaubt ist aber y != epsilon gelten muss? ist das nicht das gleiche?
Danke
Dieses Video ist sehr gut
Idee/Frage - eventuell kommt das im Video auch nicht ganz rüber. Weil allein einen Zustand mehrfach besuchen ist ja nicht der ausschlaggebende Punkt ob eine Sprache erkennbar ist oder nicht.
Ich kann doch a^n b^n mit sich selbst aber reverse kombinieren b^n a^n, dann hätte ich eine äquivalente Sprache (ab)^n (ba)^n und die ist erkennbar, in den Zustand 1 komme ich nur mit (ab) und bleibe dort mit (ab) und nur mit (ba) wechsle ich in den akzeptierenden Zustand 2, was dort passiert ist dann eigentlich egal, weil es sonst vorher schon geknallt hätte. Damit (knallen) wären die anderen Zustände in 1 gemeint die in den Papierkorb führen (), (a), (b), (aa), (bb)
Ansonsten ist natürlich klar das allein oo (Unendlich) was auch immer nicht erkennbar sein kann, weil ich dann oo lange warten muss, was ich nicht kann (praktisch nicht kann)
Im Umkehrschluss heißt es dann aber auch, das alles erkennbar ist, weil ich immer eine endliche Eingangsgröße habe. Alles andere wäre doch ziemlich sinnfrei, ein unendlich rechnender Automat endet nie. Schon a^n wäre nicht erkennbar, wenn n beliebig groß sein kann, irgendwann kommt vielleicht doch ein b, aber ich werde es unter Umständen nicht erfahren. Ich muss also die Eingangsgröße sinnvoll begrenzen.
danke Chef
Vielen Dank für deine super Erklärungen. Da wir im Corona-Semester Screencasts statt Vorrechnen machen müssen und ich deine von der Qualität her echt mega finde folgende Frage: Wie gehst du vor, dass du einen durchgehenden Redefluss hast und größere Zeichnungen dann ganz schnell erscheinen? Machst du da beim Aufnehmen ne Redepause, zeichnest und machst dann weiter und schneidest die Pausen dann am Ende raus? Das ist ja ganz schön Aufwand? Lohnt sich aber sehr, da du sehr angenehm durchsprichst und man nie lange auch irgendwelche Zeichnungen warten muss!
Genau, ich mache Pausen und schneide viel raus, sogar möglichst die "Ähhhm" zwischendurch, und ich spreche die Sätze oft mehrfach, bis ich damit zufrieden bin. Die Aufnahme ist meistens 3-4 mal so lang wie das fertige Video.
danke
Sehr gut erklärt :) das Original hatte ich nich ganz kapiert, aber jetzt ist es klar ':D
Na dann hat es sich ja gelohnt! :)
wow danke mega gut erklärt, ich glaube nur da ist dir ein fehler unterlaufen, nämlich ist der eine zustand in den du zwei mal läufst, der rot auf grün zustand, da müsste man theoretisch mit b weitermachen wenn ich mich nicht täusche. Aber ändert an sich jetzt nicht allzu viel am Ganzen. Hatte mich nur eingangs etwas verwirrt
Kann mir jemand erklären, warum man nicht den Mittelteil also aabb nehmen kann und aufpumpen? Dann würde es auch nicht zur Sprache gehören, weil aaaaabbaabbbbbb nicht zur Spräche gehört? Wäre das genau so richtig? -> ist y beliebig wählbar?
Super Video!! Jedoch ist der Automat am Anfang etwas missverständlich für dein Beispiel. Der Weg denn wählst mit den "a"s geht ja durch einen akzeptierenden Zustand. Leeres Wort akzeptierender Zustand und ansonsten darf der letzte Zustand ja nur mit b erreicht werden... Vielleicht bin ich aber auch zu penibel;) Das Video ist trotzdem mega hilfreich!!
Sehr gut beobachtet! Ist mir auch im Nachhinein aufgefallen, aber nochmal aufnehmen wollte ich es deswegen nicht.
@@NLogSpace Ist glaube ich auch nicht wesentlich für das Verständnis! Während du das im Bild erklärst, wird der Automat ja auch nur indirekt thematisiert. Ist ja eh unabhängig von dem Beispiel erklärt! Video ist echt top!
Hallo, super erklärt! Eine Frage ist mir geblieben: 9:05 hier sagst du, dass x und y maximal so lang wie p sein kann. Müsste es nicht heißen x und y kann max die Länge von z haben?
Nein, ich meine dort wirklich p und erkläre im folgenden Satz auch warum: Die Zahl p ist die Anzahl der Zustände des Automaten. Nach höchstens p Symbolen müssen wir also einen Zustand doppelt besucht haben. Somit können wir x und y so wählen, dass sie zusammen höchstens p lang sind.
@@NLogSpace Erstmal mega gut erklärt habe es dank dir endlich verstanden, nur eine Frage hab ich auch zu dem Thema, du meinst sie müssen höchstens p Lang sein und definierst ja auch | xy|
Hey,
Danke erstmal für die gute Erklärung! Ich habe morgen eine Klausur und du hast mir sehr geholfen.
Ich hab aber noch eine Frage, und zwar sagst du man kann y beliebig oft aufpumpen, auch 0 mal um das wort xz zu bekommen. Aber da y ja nie das leer wort sein darf ist das doch falsch oder? (also y ungleich ϵ)
Vielleicht kann mir heute dazu noch jemand helfen?
Lg Tom
In der Zerlegung w=xyz ist das y niemals das leere Wort. Aber das "gepumpte" Wort xy^iz ist ein anderes Wort. Wir können hier auch i=0 wählen und dann bekommen wir das Wort xz. Das y ist immer noch nicht leer, es kommt bloß in dem Wort xy nicht mehr vor.
@@NLogSpace Danke, echt Super!
Für alle die es trotzdem nicht verstanden haben. Denkt es euch so: die route über y ist da, also die grüne Route in der Zeichnung, wenn wir aber wollen müssen wir sie ja nicht gehen. Es ist aber wichtig dass sie existiert.
Gut gesagt!
Was ist wenn ich einen DEA mit zwei Zuständen habe und man beispielsweise mit dem Buchstaben a vom Startzustand in den zweiten Zustand (der auch der Endzustand ist) geht. Dann wird ja lediglich das 'a' vom Automaten akzeptiert, ich kann es nicht aufpumpen aber es müsste ja trotzdem erkennbar/regulär sein oder...?
Das Pumping Lemma sagt ja nur, dass alle Worte ab einer gewissen Länge sich pumpen lassen. Wenn Du zwei Zustände hast, dann wären es alle Wort ab Länge 2. Aber davon gibt es keine in der Sprache {a}. Aber wenn der DEA oder NEA mit 2 Zuständen noch weitere Worte von Länge mindestens 2 akzeptierten würde, dann würden die sich pumpen lassen.
@@NLogSpace Verstehe 💡 Vielen Dank für die Erklärung und die schnelle Antwort 🥰
Ehrenmann
Extrem gut erklärt! Ich habe es endlich verstanden.
Meine Aufgabe ist es aufzuzeigen, dass eine Grammatik zweifach 4-aufpumpbar sind
Doch was heißt das ?
In der Minute 11:22 bedeutet das i neben dem Y, in meinem Fall die 4 (Aufpumpbar)? und was bedeutet das zweifach ?
Ich weiß nicht, was das beudetend soll. Sollte wohl in der Aufgabe oder in der Vorlesung definiert sein!
Ich hätte noch eine andere Frage: Bei uns hatten wir in der Bedingung, dass entweder xy^iz in L oder für alle i nicht drin ist. Den zweiten Teil verstehe ich nicht ganz...
Hmm, ich weiß auch nicht. Das kann ja gar nicht für alle i nicht in L sein, denn für i=1 ergibt sich das ursprüngliche Wort w, und das kommt ja aus L. Oder habt ihr vielleicht eine Version, wo w nicht aus L gewählt wird?
@@NLogSpace Ah ja! w darf aus allen möglichen Worten gewählt werden. Danke dir!
Der CE-Student in mir fragt sich "Ok, welche Sprache ist jetzt erkennbar? C++ oder Python? Java garantiert nicht"
XDD
Ok wieso |xy|
ist das pumping lemma nicht da, um zu zeigen, dass eine sprache nicht *regulär* ist ? Ich bin verwirrt da du immer "erkennbar" sagst, was ja Typ 0 in der Chomsky-Hierarchie entspricht, aber ruglär meint Typ 3 in der Chomsky-Hierarchie.
Edit: Ich habe nochmal in meinen Unterlagen nachgeschaut und es ist jede von einem endlichen Automaten akzeptierte/erkennbare Sprache regulär. Somit stimmt es scheinbar doch was du sagtest. Aber irgendwie trotzdem verwirrend^^
Ich nutze das Wort "erkennbar" synonym zu "regulär", das ist auch das gleiche wie Typ 3. Falls es um Typ 0 geht, würde ich sagen Typ 0 oder Turing-erkennbar.
@@NLogSpace Ach so danke dir :D schreibe in 20 Tagen Klausur und deine Videos retten mich gerade :-D unser Prof erklärt nur extrem mathematisch und du schön anschaubar. Das ergänzt sich beides sehr gut !