Formale Sprachen #33 - Kettenregeln entfernen

[@HerrSchmiddi]

Mein Freund, du bist das beste was mir heute über den weg gelaufen ist.

[@matthiasbretting6486]

Auch noch 5 Jahre nach Veröffentlichung deines Videos hilft es mir, meine Hausaufgaben perfekt zu lösen und zu verstehen. In der Vorlesung wird das Formal ohne Beispiel gemacht, es hat ewig gedauert und man hat es deswegen direkt vergessen, weil man es nicht verstanden hat. Ein Video später und man weiß nicht nur wie es geht, sondern auch warum! Danke dir

[@DailyShit.]

Verstehe nicht wieso man Sachen nie an Beispielen erklären kann. Das ist ja wie Ärzten im Studium immer nur vom Körper zu erzählen aber keine Bilder oder Abbildungen zu zeigen.

[@Winterbeere48]

Danke für die ganzen Videos.

[@Bibbs420]

Deine Videos sind echt spitze erklärt! Hilft mir ungemein, jetzt in der Prüfungszeit. Weiter so!

[@dk9469]

Absolut genial! Hat mir mein Studium sehr viel einfacher gemacht! Grüße von der TU Darmstadt!

[@Zeitverschwendung]

gerade entdeckt, bin ich froh, dass es dich gibt!

[@ELBARTOmovies]

Ab 14:00 hat es mich geflashed, da ich endlich den Zusammenhang zwischen diesem Thema und CYK-Algorithmus verstanden habe :D

[@seldilein9597]

Super erklärt! Daumen hoch. Dazu noch eine stimme der man gerne zuhört . Danke

[@snackm4515]

Danke für deine Videos zum Thema Chomsky Normalform, sie haben mir sehr geholfen!

[@XaiterMOG]

Wunderbare Erklärungen und besser als jede Vorlesung, weiter so !!

[@holgerwalbert7967]

Auch vielen Dank für die tollen Erläuterungen in den ganzen Videos, helfen wirklich gut, um den manchmal doch sehr theoretischen Text im Studium zu verstehen

[@dazzle5350]

Vielen Dank für die Videoreihen, die du super erklärst und darstellst! Sie helfen sehr beim Lernen für die TI-Klausur haha :D Es wäre klasse, wenn du eventuell noch ein Video zur Greibach-Normalform erstellen könntest! Ansonsten weiter so, deine Videos sind wesentlich verständlicher als in so manchen Übungen!

[@DJDomik]

Sehr gut erklärt, verstehe es bei dir deutlich besser als in der Vorlesung. Danke :)

[@dajennjeya2825]

Vielen Dank für deine Videos! Super erklärt und vor allem sehr verständlich und man kann alles sehr gut nachvollziehen. Daumen hoch!!

[@Seff2]

Danke für die Videos zu CNF. Haben sehr geholfen.

[@toastbri4007]

Du machst mir die Prüfungszeit wesentlich einfacher - VIELEN DANK! :)

[@vatoslocos9960]

Geiles Video vor allem das Quiz sehr sehr nice Goldwert.

[@NLogSpace]

Danke! Ja ich denke auch, dass solche Fragen zum Mitdenken sehr hilfreich sind. Ich werde versuchen, mehr davon zu bringen.

[@Whoo0o0]

Super Videos, wirklich. Vielleicht hab ich es überhört, aber zur Anzahl der Schritte kann man noch sagen, dass es in CNF immer 2n-1 Schritte sind. (n=Länge des Wortes)

[@ReddDevil1982]

Frage zum Ende der Eliminierung der Kettenregeln: S -> Ta | bTb | a | aSb | b | ab | ST T -> bTb | a | aSb | b | ab ST R -> aSb | b U -> ab | ST Du hast jetzt hier im Endeffekt in S => T,R,U eingesetzt in T => hast du R und U eingesetzt. Könnte man damit nicht am Ende der Ketteneliminierung R und U weglassen. Da diese ja bereits komplett in S und T enthalten sind?

[@Boogeyyyman]

Perfekt erklärt. 😀😎Warum machen viele Profs es nicht so🤦‍♂️

[@midnightmariechen]

super Videos! Perfekt als Vorbereitung auf meine mündl. Prüfung in Theoretischer Informatik :-)

[@fluury]

Danke für das Video!

[@iharbakhanovich]

Danke. Wie immer super

[@erwrwer8695]

Danke führst mich ein bissel durch meine Prüfung für theoretische informatik

[@nocodenoblunder6672]

überragendes Video

[@NikitaBalyschew]

Hi, super erklärungen, vielen Dank. Nur eine kleine Anmerkung die Regel R und U können weg, da sie nicht mehr abgeleitet werden können.

[@NLogSpace]

Richtig, gut gesehen! Im Allgemeinen kann mir immer alle Regeln entfernen, in denen ein Nichtterminal vorkommt, das - vom Startsymbol aus niemals abgeleitet werden kann, oder - aus dem man kein Terminalwort ableiten kann. Wenn man solche Regeln entfernt, dann bleibt die davon erzeugte Sprache die gleiche.

[@FloPfeifer]

Stark!! Danke!

[@cn-ml]

Sehr gut erklärt, vielen dank :)

[@piejecko]

Gutes Video. Kurze Frage zur mathematischen Sicht bei 8:37 und zwar: Möchte ich die Menge M definieren - und zwar so: V := Menge aller Nicht-Terminale (NT) M := { (x, y) | x, y ∈ V x =>* y } M definiert also, dass man in endlich vielen Schritten von einem NT zum anderen kommt. Kann man doch so machen, oder?

[@christianpi500]

Danke bist a guader Mo!

[@synomai2990]

Erstmal Danke für deine Videos, du erklärst den Stoff sehr einprägsam. Zu der Herstellung der Chomsky-Normalform habe ich nur eine Anmerkung. Laut unserer Vorlesung ist die Reihenfolge wichtig, da sonst eine Grammatik in CNF produziert werden kann, die exponentiell größer als G ist. In der Vorlesung wird die gleiche Reihenfolge wie auf Wikipedia (de.wikipedia.org/wiki/Chomsky-Normalform) beschrieben,verwendet.

[@NLogSpace]

Stimmt, das ist mir gar nicht aufgefallen! Mit der Reihenfolge, die ich hier vorstelle, kann man tatsächlich eine exponentiell größere Grammatik bekommen, was dann die Komplexität beeinflussen würde. Ich glaube der entscheidende Punkt ist, ob man Epsilon-Regeln vor oder nach dem Verkürzen entfernt. Wenn man nämlich zuerst die Epsilon-Regeln entfernt (so wie ich es im Video gemacht habe), dann können exponentiell viele Regeln dazukommen. Beispiel: S -> ABCDEFGH, A->ε, B->ε, C->ε, D->ε, E->ε, F->ε, G->ε, H->ε. Wenn man erst Epsilon-Regeln entfernt, dann muss man für die erste Regel 2^8-1 viele neue Regeln einführen, d.h. eine neue Regel für jeden nicht-leeren Teilstring von ABCDEFGH. Die Reihenfolge von Wikipedia ist also besser, die entspricht hier 3->4->1->2.

[@leqitsweden1943]

Alter die Überraschung als er plötzlich ein Mikrofon auspackt, bei dem meine Ohren nicht sofort Selbstmord begehen xD

[@boushkeenshekho6978]

Ich bedanke mich für die ausführliche deutliche Erklärung. Ich hätte bitte Paar Fragen. wie haben Sie in den vierten Frage 9 Ableitungen bekommen? Könnten Sie bitte die Lösung von den Vierten Frage ausführlich Schritt für Schritt schreiben?

[@Leroygames]

S -> CC C -> CA | AB | BA A -> a B -> b 1. S -> CC => CC 2. C -> CA => CAC 3. C -> BA => CABA 4. C -> AB => ABABA 5. A -> a => aBABA 6. B -> b => abABA 7. A -> a => abaBA 8. B -> b => ababA 9. A -> a => ababa Hoffe das hilft

[@melo1337king]

Danke.

[@NLogSpace]

@@melo1337king da nich für!

[@khalidshiba970]

Danke sehr

[@user-xp5lv5zc5n]

Falls im vorigen Schritt S0 -> S | epsilon hinzugefügt wurde, zählt das auch als zu bearbeitendes Paar? Danke

[@benkoger2065]

Danke, endlich ein neues Mikro🙌

[@huhuboss8274]

Danke :)

[@ege6142]

THANK YOU THANK YOU THAK YOU SO MUCH

[@rizzy--]

Was mache ich wenn ich zu viele Terminale habe? Wir haben eine Aufgabe bekommen wo wir die folgende Grammatik in die CNF umwandeln mussten: A --> B, CD, a B --> C, aa C --> D, BD D --> aaa, aaaa, aaaaa Wie sehen die Produktionsregeln dann aus? Lässt man dann B und D vollständig weg oder wie geht man da vor? :D

[@rizzy--]

Danke, für die Antwort

[@lucasludtke4021]

frag ich mich auch ? :)

[@jessica1039]

Wäre die Ableitung bei der 4 nicht bei 7? S --> AX1 a X1 --> BX2 b X2 -->AX3 a X3 --> B X4 b X4 -->A a A = a B = b

[@7_9]

Ich würde behaupten, man braucht 6 Schritte: S -> AX1 X1 -> BX2 X2 -> AX3 X3 -> BA A = a B = b

[@easymoney1226]

man muss jedes ableiten von A und B zu a und b als einen schritt interpretieren i guess

[@begimaiakylbekova254]

Die Videos sind auch heute aktuell. Kannst du mir sagen, weilche tool benutzst du für Erklärung? Wie heißt diese App? Danke im Voraus:)

[@NLogSpace]

Danke! Das Tool heißt Xournal, ist ein Linux-Programm.

[@begimaiakylbekova254]

​@@NLogSpace Danke schön! Vielleicht kennen Sie andere Tools, die relativ neu sind und für Windows passen. Schlagen Sie was mir vor:)

[@timi-mc1xt]

Danke sehr gut erklärt, mir fehlt nur noch die Ergänzung wenn man Kreise hat, dass man diese auch entfernt bevor man dann die Ketten entfernt.

[@NLogSpace]

Ich sehe nicht wo die hier vorgestellte Methode fehlschlägt, wenn man Kreise hat. Ich denke also es ist nicht notwendig Kreise extra zu behandeln, oder?

[@timi-mc1xt]

@@NLogSpace fehl schlägt die Methode nicht, aber wenn man A -> B, B -> C und C -> A hat sind die 3 Nicht-Terminalsymbole äquivalent und somit 2 davon redundant. Dies kostet mehr Zeit und unnötige Arbeit.

[@NLogSpace]

Achso, also das ist eine Optimierung, die vielleicht in der Praxis gemacht wird, aber wir sind hier nur an der Theorie interessiert. Insbesondere ändert das Entfernen von Kreisen auch nichts an der Komplexität: Ob mit oder ohne Kreise, man hat O(n^2) viele Paare, die man abarbeiten muss.

[@hayfay6851]

Wäre es grundsätzlich nicht sinnvoller, bei der Überführung in CNF, die Schritte in Reihenfolge 3,4,1,2 abzuarbeiten?

[@NLogSpace]

Richtig, das hatte schonmal jemand vorgeschlagen (siehe Kommentar von Synomai). Der Grund ist, dass man mit der Reihenfolge 1, 2, 3, 4 eine exponentiell größere Grammatik erhalten kann, während man mit 3, 4, 1, 2 eine von höchstens polynomieller Größe bekommen. Für praktische Zwecke ist also 3, 4, 1, 2 besser geeignet, für theoretischen Zwecke ist es egal. :)

[@matzus1574]

soooo gut

[@JoergMcFly]

Bonuspunkte für den Fluxkompensator 😎

[@tobiasb.3966]

Gutes Video

[@muskelgurke1194]

Jetzt bestehe ich AFS !!

[@idzh-t7s]

Ich will dir was spenden. Hast du Paypal? Bitte nicht die Videos löschen oder ein Backup erstellen . Du bist ein Heiliger :D für uns Studenten.

[@NLogSpace]

Danke für das Lob, das freut mich, dass Dir die Videos gefallen! Link für Spenden ist in der Videobeschreibung. :)

[@mdg8037]

Warum braucht man 4 Ableitungsschritte? kzbin.info/www/bejne/iYmlpXmIeKpssKM

[@NLogSpace]

Das erkläre ich in einem der vorigen Videos ("Chomsky-Normalform herstellen", am Ende).

[@Necrobin]

Mikro upgrade 💯