Formale Sprachen #32 - Epsilon-Regeln entfernen
Вставка
- Опубліковано 1 бер 2017
- Als weiteren Schritt zum Herstellen der Chomsky-Normalform entfernen wir die Epsilon-Regeln. Hierbei ist zu beachten, dass das leere Wort von einer Grammatik ohne Epsilon-Regeln nicht mehr erzeugt werden kann.
Grade wie vermutlich 90% der Zuschauer dieses Videos in Prüfungsvorbereitung für Theoretische Grundlagen der Informatik - einfach nur DANKE!
Da sitzt man als Student mitten in der Lernphase und ist so heilfroh, dass es solche tollen Videos wie das hier gibt. :D
Danke danke danke
Bei diesen Videos habe ich immer das Gefühl, es ist ganz einfach. Und kann es dann auch wirklich. Perfekte Ergänzung zu Skript und Vorlesung, besonders zur Klausurvorbereitung und um Lücken zu schließen. SUPER!
Perfekt erklärt! Hab's mit dem Video super schnell verstanden. Wünschte du wärst mein Prof gewesen ...
1. 1,5x Wiedergabegeschwindigkeit
2. Leise Hintergrundmusik anmachen (White noise)
3. Ein ganzes Semester Theo innerhalb eines Tages gut erklärt bekommen und verstehen
4. Klausur (hoffentlich) bestehen
Und das alles umsonst. Vielen Dank dafür!
und bestanden? :D fahre die Reihenfolge gerade genauso
Wo ist Schritt 5: ??? Und schritt 6: profit ?
Richtig gute Erklärung! Angenehmes Tempo, ausführlich erklärt, schön Schritt für Schritt, vielen Dank!
10:36 Ich musste an der Stelle iwie so lachen :D
Übrigens will ich noch Danke sagen. Hast mir dieses Semester sehr geholfen und sehr viel Arbeit erspart. Ich hab morgen meine Prüfung und bin relativ sicher, dass ich sie dank deiner Videos schaffe :)
:D
mega korrekt das du das dass mit dem Epsilon gesagt hast bei uns machen wir das so. Erklärst echt gut muss man sagen👍
Es ist zum Glück kein allzu schweres Thema, aber danke für die Erklärung! Gutes, verständliches Video.
wow, einfach gut erklärt. Liebe deine Videos.
Deine Videos sind alle super, danke!
Ganz gut geklärt !
Danke sehr :)
Auch von mir ein dickes Dankeschön für deine Videos! Einfach, ruhig und verständlich erklärt. Du solltest Dozent werden, falls du das noch nicht bist :-) Das Video zu den Kettenregeln, würde mich auch sehr interessieren.
Danke dir!
Hallo Leif, wir haben gerade das Prüfungsfach Softwareentwicklungsumgebungen. Deine Videos zum CYK-Algoithmus und de Chomsky Normalform sind echt super! Frage: Kannst du auch ein Video über Parsergeneratoren (Konkret Javacc) erstellen, oder uns Tipps geben?
Sehr gute Videos! Danke Dir! Eine Frage: Ich verstehe nicht wirklich, warum R nicht auch in die Menge gehört. Ich sehe da keinen Unterschied zu den anderen in der Menge enthaltenen Elementen.
08:41 Schade eigentlich! 😂 Naja, hat trotzdem Spaß gemacht.
Rückfrage:
Gut erklärt!
Sehr cooles Video. In dem Buch (Theoretische Informatik, Hoffmann) was ich lese wird die CNF so definiert: "Eine Grammatik G = (V, Σ, P, S) liegt in Chomsky-Normalform vor, wenn alle Produktionen die Form S → ε, A → σ oder A → BC besitzen mit A ∈ V , B,C ∈ V \{S} und σ ∈ Σ."
klasse!!!
Hey Leifaktor,
super Videoreihe, hat mir schon sehr weitergeholfen!
Eine frage hätte ich noch. Warum ist R nicht in der Menge M?
Kann ich nicht so ableiten(£ steht für epsilon)?
R->bbS->rbbTT->rbb£
Somit habe ich doch R nach epsilon ableiten können, oder?
Es geht nicht darum, dass man aus R irgendein Wort ableitet, in dem Epsilon als Teilwort vorkommt, sondern darum, das Wort Epsilon abzuleiten. In deinem Beispiel hast Du aus R nicht das leere Wort abgeleitet, sondern das Wort bb (das kleine r davor ist falsch). Wir bräuchten also eine Ableitung R -> ... -> Epsilon. Aber solch eine gibt es nicht. Für S, T und U hingegen ist das möglich, daher sind diese in der Menge M, aber R nicht.
Stand zwar schon oft in den Kommentaren deiner Videos,aber ich wollte es auch nochmal selbst sagen:
Danke, du hast mir hier echt den Arsch gerettet. Weißt du zufällig schon wann das Video zu den Kettenregeln rauskommt? Ich hab am 31.3 das Fachgespräch in Theo 1(genau genommen die Wiederholung vom Fachgespräch, weil ich es schon mal verhauen habe) und versteh das im Skript so gar nicht.
BTW hab gelesen du hast auch in Bremen studiert, hattest du zufällig auch theo 1 oder irgendwas anders bei Thomas?
Erstmal danke für die super Erklärung aber eine Frage habe ich leider noch.
Bei S -> aSa | bSb | AcA
A -> aAb | B
B -> bB | cB | epsilon
Kommt hierbei "A" auch in die Menge M?
Da "A" nicht das leere Wort erzeugen kann.
Nach seiner Erklärung ist dein A in der Menge M enthalten. Ich vermute mal dass du jede einzelne Variable einmal als Startvariable sehen sollst, sonst könnte man U in seinen Beispiel (2:14) gar nicht als das leere wort ableiten wenn man von S als Startvariable ausgeht. Da hätte man folgende ableitung bekommen:
S -> aUb -> aSTSb -> aTTTSb -> aTTTTTb -> ab
Was dann nicht das leere Wort entspricht, und er hat stattdessen dieses hier gemacht:
U -> STS -> TTTS -> TTTTT -> epsilon
Also in deinem Beispiel hättest du dann:
A -> B -> epsilon
Was genau das leere Wort entspricht
Gutes Video
Eine Frage (vielleicht hab ich das auch überhört) was ist wenn wir eine epsilon-Regel haben der Form T-->epsilon, ohne, dass wir T--> bR | epsilon haben? Also wirklich nur das epsilon. Faellt dann die ganze Regel weg? Was passiert dann mit den anderen Regeln, die das T enthalten? 🤯
Ja, wenn man nur T -> ε hat, dann fällt die ganze Regel weg. Wenn man nach dem Entfernen der ε-Regeln und Einführen der Abkürzungsregeln dann also keine Regel mehr für T hat, dann kann man auch alle anderen Regeln entfernen, die T enthalten (muss man aber nicht).
@@NLogSpace Danke für die schnelle und hilfreiche Antwort! :)
Hallo, super Videos :) Ich schreib nächste Woche meine THI Prüfung und würde was zur Matrixklauselformel suchen, kannst du da auch ein Video dazu machen?
Hallo, danke! :)
Also Matrixklauselformel sagt mir nichts, kann es sein, dass das etwas aus dem Bereich Logik ist? Wenn Du mir Material dazu schickst, dann könnte ich mal darüber nachdenken. Aber bis nächste Woche wird das definitiv nichts, bin schon sehr beschäftigt im Moment, tut mir Leid!
Ja gehört zur Prdäikatenlogischen Resolution, Prädiaktenlogik und Normalformen: Hab online grad nur was von einer deutschen Uni gefunden.. ls1-www.cs.uni-dortmund.de/images/user/logidac/tick/Lehre/13WS/Logik/12WS-logik-folienskript.pdf - Kein Stress, sollte ich nochmal antreten müssen hab ich ja noch ne Chance ^^
Ah, alles klar. Ja zu Logik würde ich sogar gerne eine ganze Serie machen, aber alles zu seiner Zeit. :)
Kann mir jemand erklären warum aus R nicht Epsilon abgeleitet werden kann? R -> bbS -> bbTT -> bb ist das ein Fehler oder verstehe ich den Algo fasch? TImestamp 3:10
Epsilon ist das leere Wort. Jede Regel für R erzeugt sofort ein Terminal. Die Regel R -> bbS erzeugt zwei mal das Terminal b. Die andere Regel R -> RSUa erzeugt das Terminal a. Sobald ein Terminal erzeugt wurde, handelt es sich nicht mehr um das leere Wort.
kann man nicht bei der R-Regel alle non Terminale nicht weglassen damit nur a produziert wird, weil man ja alle combis durchgehen muss oder nicht ? send help XD
hätte man bei R nicht noch RSU fallen lassen können-> a und noch R wegfällt -> SUa und RS wegfällt ->Ua
warum hast du die SS sehr betont gesagt xdxdxd
2:56
Mir ist nicht klar warum wir nicht R genommen haben wir konnen immer noch von R auf Epsilon kommen
R=>bbS=>bbaUb=>bbaSTS=>bbaS(epsilon)TS
Nun habe ich ein epsilon in der mitte des wortes stehen
Es geht nicht um Worte, die epsilon enthalten, sondern nur um das Wort epsilon. Wir suchen die Nichtterminale, aus denen wir genau das leere Wort epsilon ableiten können. Das Wort bbaSTS ist nicht epsilon.
Vielen vielen Dank!
TI ist das Langweiligste was ich je in meinem Leben kennenlernen durfte.
:'(