Formale Sprachen #25 - Pumping-Lemma für kontextfreie Sprachen
Wir zeigen das Pumping-Lemma für kontextfreie Sprachen, mit dem wir später zeigen wollen, dass es Sprachen gibt, die nicht kontextfrei sind.
Wir zeigen das Pumping-Lemma für kontextfreie Sprachen, mit dem wir später zeigen wollen, dass es Sprachen gibt, die nicht kontextfrei sind.
Пікірлер: 39
es ist echt krass, dass du dir die mühe machst sone videos zu produzieren und offensichtlich richtig vielen leuten damit krass hilfst. danke dafür!
Deine Videos sind perfekt, danke! Gerade jetzt, wo man in Corona-Zeiten auf Seminare/Übungsstunden verzichten muss....
Die beste Erklärung die ich je gesehen hab! Danke!
So gut erklärt. Du schaffst es, dass man direkt eine Intuition entwickelt, so sollte es sein.
Du rettest Leben, danke aus München
Wär echt cool wenn du weiter machst mit den Videos, kannst es super erklären.
@NLogSpace
7 жыл бұрын
Ich werde auf jedem Fall weitermachen, ich habe zur Zeit nur leider technische Schwierigkeiten bei der Video-Aufnahme (Audio wird immer wieder asynchron zum Video). Aber ich versuche das möglichst schnell in den Griff zu kriegen!
Grottig erklärt im Skript, chaotisch erklärt in der Vorlesung von Professorin, aber wie immer gut erklärt auf KZread! Danke dafür!
Die Erklärungen sind alle super ! Ich habe in den Vorlesungen meiner Uni (Bayern, also wohl nicht deine:D) nicht alles verstanden und du erklärst es nocheinmal sehr verständlich, danke dafür :)
Einfach klasse !!!! Danke !!!! :)) Das beste Video über PumpingLema !!!
Vielen Dank für deine Videos! Du kannst wirklich super gut erklären. :)
tolle videos, vielen danke dafür!
Die Erklärung ist prima! Vielen Dank!
Hey, deine Stimme habe ich doch schon in Seminarräumen einer deutschen Hansestadt (will deine Identität nicht aufdecken xD) im Rahmen eines Tutoriums gehört, oder irre ich mich? Super Videos. Perfekt um sich auf Fachgespräche vorzubereiten. Kurz und bündig erklärt. Vielen Dank
@NLogSpace
9 жыл бұрын
Haha, du irrst dich nicht. :D Viel Erfolg beim Lernen!
@Luca__
8 жыл бұрын
+Leifaktor Ist es Bremen? Da studier ich grad im ersten Semester und die Inhalte deiner Videos und meines ersten Semesters decken sich schon sehr ^^
Gute Erklärung danke!
Vielen Danke! Hat mir sehr geholfen!
Ehrenmann!
Por fin encontre una explicacion con sentido.. muchas gracias = Endlich habe ich eine verständliche Erklärung gefunden.. vielen Dank :)
@NLogSpace
5 жыл бұрын
de nada :)
Stark!
Wieder einmal ein sehr gutes Video! Darf ich fragen, ob du (Informatik) studiert hast, oder ob du dir alles im Selbststudium erarbeitest hast?
@NLogSpace
Жыл бұрын
Danke! Ich habe Mathematik studiert, aber habe mich viel für theoretische Informatik interessiert. Habe nach dem Mathestudium in theoretischer Informatik promoviert und danach noch ein paar Jahre an der Uni geforscht und gelehrt.
Weiß nicht, wie man es besser erklären könnte. Klasse
Moin, wolltest du nicht eigentlich den Schnitt von zwei Typ-2 Sprachen zeigen?
Ist ein Strukturbaum == was du Ableitungsbaum nennst? Und was ist eine rekursive Inferenz? Wenn du das Grundkonzept in so kurz wie möglich runterbrechen könntest, das wäre sehr nice.
@NLogSpace
7 жыл бұрын
Mir sind die Begriffe "Strukturbaum" und "rekursive Inferenz" nicht geläufig. Aber ich habe gegooglet und es scheint so, als wäre ein Strukturbaum das gleiche wie ein Ableitungsbaum. Und rekursive Inferenz scheint eine Art Beweis zu sein, dass ein Wort von der Grammatik erzeugt wird, bei der man aber nicht vom Startsymbol zum Wort geht, sondern mit dem Wort beginnt und die Ableitungsregeln rückwärts anwendet, bis man nur noch das Startsymbol hat. Aber wie gesagt, die Begriffe sind mir noch nie untergekommen, also keine Garantie!
@a.y5742
7 жыл бұрын
Vielen Dank! Die erklärung habb ich gesucht. Noch eine Frage: Kann es sein, dass man bei Sturkturbäumen gar nicht sehen kann, dass man Linksableitung/Rechtsableitung benutzt hat? Ich meine, wenn ich ein bestimmtes Wort erzeugen soll, kann man ja bei einem Baum schlecht darstellen, dass man Links/Rechtsableitung benutzt hat. Oder gibts nen Unterschied bei Ableitungen von Links und Rechtsableitungen (ausser dass man bei der Rechtsableitung die "rechteste" Nicht-terminale zuerst abgeleitet hat)
@NLogSpace
7 жыл бұрын
Genau, der Ableitungsbaum (=Strukturbaum) sagt nur, wodurch jedes Nichtterminal ersetzt wurde, aber nicht in welcher Reihenfolge. Ein Ableitungsbaum entspricht also vielen verschiedenen Ableitungen, die alle zum selben Wort führen. Eine von diesen Ableitungen ist eine Linksableitung (wenn man immer erst das am weitesten linke Nichtterminal ersetzt), eine ist eine Rechtsableitung (wenn man immer erst das am weitesten rechte Nichtterminal ersetzt), aber es kann noch viele andere geben, indem man einfach irgendeine andere Reihenfolge wählt.
sry für die vllt blöde Frage, aber das Thema von diesem Video hat mit Chomsky Normalform nichts zu tun ? Weil die verwendete Grammatik ja nicht in der CNF ist. Bei mir im Skript steht aber, dass man des nur mit Grammatik in CNF nachweisen kann...hmm..
@dasten123
8 жыл бұрын
+marckotobelo 15:27 bis Ende spricht er genau darüber
@NLogSpace
8 жыл бұрын
+marckotobelo Entschuldige die späte Antwort! Wie dasten123 schon richtig gesagt hat, spreche ich diesen Punkt am Ende des Videos an. In CNF muss die Grammatik nicht unbedingt vorliegen, wichtig ist nur, dass es keine Kettenregeln gibt.
Welches Tool benutzt du zum Zeichnen?
@NLogSpace
4 жыл бұрын
Das Tool heißt Xournal.
Entweder ist ein Fehler im Video bei ca. Minute 9:13 oder ich habe ein Gedankenfehler: Es heißt, dass das Wort immer mit einem b beginnt (ja das ist korrekt) und immer mit einem a endet. Und das müsste falsch sein, denn die Regel 2 in der Menge P (S->b) erlaubt auch Wörter, die nur aus einem b bestehen.
@NLogSpace
7 жыл бұрын
Von der Grammatik wird auch das Wort b erzeugt, das stimmt. Aber die Grammatik erzeugt auch noch viele andere Wörter, und ich habe hier mit einer Ableitung des Wortes bbabaaaa begonnen. Dann habe ich den Ableitungsbaum verändert (indem ich den Teilbaum unterhalb von T an verschiedene Positionen gesteckt habe) und habe dadurch Ableitungen für andere Worte bekommen, etwa bbaaa oder bbababaaaaa. Diese Worte müssen aber natürlich nicht alle sein, die man mit der Grammatik überhaupt bekommen kann, also es ist kein Widerspruch, dass wir an dieser Stelle keine Ableitung für das Wort b bekommen.
i darf aber doch auch 0 sein, oder? Weil du hier schreibst dass es Element der natürlichen Zahlen sein muss
@NLogSpace
7 жыл бұрын
Ja, i darf auch 0 sein. Die natürlichen Zahlen werden in der theoretischen Informatik meistens inklusive der 0 definiert.