Formale Sprachen #32 - Epsilon-Regeln entfernen

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.

[@wazdalos]

Grade wie vermutlich 90% der Zuschauer dieses Videos in Prüfungsvorbereitung für Theoretische Grundlagen der Informatik - einfach nur DANKE!

[@brucemozart3665]

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

[@lukasebner9867]

Perfekt erklärt! Hab's mit dem Video super schnell verstanden. Wünschte du wärst mein Prof gewesen ...

[@arnoclaude317]

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!

[@felixonwater]

und bestanden? :D fahre die Reihenfolge gerade genauso

[@feschber]

Wo ist Schritt 5: ??? Und schritt 6: profit ?

[@a.-f.hausmann7990]

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!

[@isown8131]

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 :)

[@NLogSpace]

:D

[@mahatma_randy123]

Richtig gute Erklärung! Angenehmes Tempo, ausführlich erklärt, schön Schritt für Schritt, vielen Dank!

[@player_player_sw3815]

mega korrekt das du das dass mit dem Epsilon gesagt hast bei uns machen wir das so. Erklärst echt gut muss man sagen👍

[@SunshineFromWithin]

Deine Videos sind alle super, danke!

[@123Rustyspoon]

wow, einfach gut erklärt. Liebe deine Videos.

[@DaiquiriFlavour]

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.

[@goeuldi]

Es ist zum Glück kein allzu schweres Thema, aber danke für die Erklärung! Gutes, verständliches Video.

[@AM-ku9cw]

Ganz gut geklärt ! Danke sehr :)

[@mit-zwiebel]

Danke dir!

[@tomu890]

08:41 Schade eigentlich! 😂 Naja, hat trotzdem Spaß gemacht.

[@nocodenoblunder6672]

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

[@NLogSpace]

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.

[@florianzimmermann6928]

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?

[@ReddDevil1982]

Rückfrage: Gut erklärt!

[@matzus1574]

klasse!!!

[@nayjer2576]

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 σ ∈ Σ."

[@TheJonas1508]

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.

[@kirby100697]

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

[@gigi19994]

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? 🤯

[@NLogSpace]

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).

[@gigi19994]

@@NLogSpace Danke für die schnelle und hilfreiche Antwort! :)

[@duesenberger]

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.

[@shadowuser1979]

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?

[@NLogSpace]

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.

[@mitchelsteel8501]

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

[@martinalindenhofer4737]

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?

[@NLogSpace]

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!

[@martinalindenhofer4737]

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 ^^

[@NLogSpace]

Ah, alles klar. Ja zu Logik würde ich sogar gerne eine ganze Serie machen, aber alles zu seiner Zeit. :)

[@tobiasb.3966]

Gutes Video

[@ManOfTheWeek596]

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?

[@JohnZakaria]

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

[@NLogSpace]

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.

[@JohnZakaria]

Vielen vielen Dank!

[@drstoned8523]

hätte man bei R nicht noch RSU fallen lassen können-> a und noch R wegfällt -> SUa und RS wegfällt ->Ua

[@arminleo]

goat

[@invoker9331]

warum hast du die SS sehr betont gesagt xdxdxd

[@alternativ1322]

TI ist das Langweiligste was ich je in meinem Leben kennenlernen durfte.

[@NLogSpace]

:'(

[@storiesbeneaththesurface1942]

@@NLogSpace Ich finde deine Videos klasse.