Formale Sprachen #31 - Chomsky-Normalform herstellen
Вставка
- Опубліковано 25 лют 2017
- Wir sehen uns zwei Schritte der Konstruktion an, mit der man eine kontextfreie Grammatik in Chomsky-Normalform bringen kann. Die Chomsky-Normalform ist Voraussetzung für den CYK-Algorithmus, welcher das Wortproblem für kontextfreie Grammatiken löst.
I can understand German better than I can understand my professor
I also have an english channel (called LeifaktorEN). Unfortunately there are very few videos yet, but i want to produce more english videos in the future.
LOL.
In unserer Vorlesung zu den Grundlagen der Theoretischen Informatik sind weitere Themen, die klausurrelevant und für uns oft nicht leicht verständlich sind, diese hier:
• Entscheidbarkeit
• Die Klassen P und NP
• Reduktionen
• Halteproblem
• o(n) und O(n)
Danke für deine Videos!
Cool, dass du wieder Videos hochlädst. Die Videoreihe von dir ist echt hilfreich im Studium, erklärst das gut :)
was ist das für ein genialer Mensch! Ich habe 2 Jahre versucht den Scheiß zu bestehen! Nun endlich verstanden!
Ich danke Ihnen vielmals für Ihre Videos . GUTE ARBEIT DANKE !!!!
Mit deinen Videos sehe ich die anstehende Prüfung schon viel entspannter
VIELEN DANK, du hast mir die Prüfung gerettet !
Vielen Dank für das Video! Hast alles sehr einfach und verständlich erklärt, habe es direkt verstanden :)
Danke vielmals für dieses hilfreiche Video!
Danke für die ganzen guten Videos! :)
Dankeschön für die Einfache klare Erklärung
Danke für die Erklärung! :)
Danke, das hilft unglaublich viel!
Wollte dich auch nochmal loben und dir für deine Mühe danken
Ich hab ein Herzinfakt bekommen als ich die Formale definition auf den Folien gesehen hab vielen Dank für das Video
Erstmal vielen Dank für Deine Mühe.. Wir Zuschauer wissen dies wirklich zu Schätzen.
Neben der Chomsky-Normalform gibt es auch die Greibach-Normalform. Ich würde mich freuen, wenn Du die auch noch besprechen könntest ^^
Wenn du weitere Themen suchst, hätte ich für Dich die (un)synchronisierten Produkte, Thompson-Konstruktionen oder Petrinetze als Vorschlag.
Super Videos! ;-) Dafür dass das Thema doch eher abstrakt ist kannst du das sehr gut erklären. Mach weiter so!
Hammer Video. Super erklärt!
Themenvorschläge : Turing Maschine, Entscheidbare und aufzählbare Sprachen 🙏
Vielen Dank!
Super Video. Die Folien der Profs an meiner Hochschule erklären es schlecht. Du hingegen gut. Alles verstanden.
Danke, war sehr hilfreich
endlich verstanden! perfektes video
geil, vielen Dank!
Danke dir!
Sehr gut erklärt
Der beste SpitzerNLogSpacer. Prima
Danke !!!!
Die Themen Berechenbarkeit und Komplexitätstheorie werden in den gängigen TI-5-ETCS-Veranstaltungen eigentlich nur angeschnitten, sind aber trotzdem wichtig (und leider meist klausurrelevant ;-( ). Hier bieten sich zumindest bei Berechenbarkeit einige dankbare Aufgabenstellungen an: a) Zu einer Sprache oder (noch praktischer) zu einem Programm eine Turingmaschine angeben. b) GOTO vs WHILE-Programme
Danke Danke Danke !!!
Also nochmal zu deinem Aufruf.: wär super wenn du Reduktion machen könntest!
Gutes Video
Themenvorschlag: PCP-Theorem
Starkes Video! Habe ich viel besser verstanden als in der Übung und Vorlesung zusammen!👩🏫
Falls ich die bevorstehende Theo-Inf Prüfung nicht schaffe, melde ich mich mit diversen Video-Vorschlägen! 😂👍
wie liefs?
Gut erklärt!
Fage: Hast du ein Video wo du erklärst, wie man diese Kettenregeln eliminiert, d. h. z. B. S -> T
Superb erklärt. 👍🏻 Vorlesungsmaterialien haben mich nicht weitergebracht.
Also für mich relevant wäre alles was in Richtung Compilerbau geht (aber das ist ja größtenteils Formale Sprachen). Außerdem: a) Deterministische kontextfreie Sprachen und darauf folgend Lösen des Wortproblems mit Kellerautomaten. b) Rechtslineare Grammatiken. Dann hast du Formale Sprachen zu 90% abgedeckt.
Wie immer ausgezeichnet! Braucht man nur noch O(n),etc., entscheidbarer Zeit (polynomiel,exponenziel,etc.), Typ 0,Typ 1 vs. andere (z.B. rechtsliniar-kontextfrei, kontexsensitive-kontextfrei,etc.),Chomsky-Schützenberger Theorem :) Dann Nobel Preis für Lehre complett ist !!!
Danke :D
Zu Typ-0- und Typ-1-Grammatiken habe ich auch Videos, die sind allerdings in der Serie über Berechenbarkeit.
Vielen Dank für die Videos, haben mir oft sehr geholfen ... aber ist das hier korrekt/vollständig? In unserem Skript und allen anderen Erklärungen zu Chomsky-NF, die ich gefunden habe, darf S ausschliesslich oben auf die linke Seite stehen, sonst (also hier) muss S in der ursprünglichen Grammatik in z.B. S' umbenannt werden, und ein neues S als Startsymbol her mit S -> S', bevor die andere Umwandlungen gemacht werden. (Ist mir gerade im Video zum CYK-Algorithmus aufgefallen).
In der Chomsky-Normalform darf S ruhig auf der rechten Seite stehen, es sei denn man hat die Regel S -> epsilon. Wenn man die Regel S -> epsilon in der Grammatik hat, dann darf S nicht auf einer rechten Seite vorkommen, dann führt man also ein neues Startsymbol ein, genau wie Du sagst. So machen wir das auch in den folgenden Videos!
Ich habe besser nachgelesen, und es scheint geteilte Meinungen zu sein. In vielen Quellen steht es eindeutig, dass S nicht auf der rechte Seite stehen darf, in anderen gilt dies nur, wenn das leere Wort dabei ist. In der Deutschen Version von Wikipedia steht Deine Version, auf der Englische wieder nicht. Spielt wahrscheinlich in der Praktik keine Rolle, aber wenn wenn es im Skript ausdrücklich so steht, könnte man bei Klausuren Probleme bekommen. Also nochmal vielen Dank!
@@3DWaiter Stimmt, manche definieren es so, manche so. Der wichtige Punkt dabei ist: Es spielt in der Praxis keine Rolle, denn man kann wie gesagt die eine Version in die andere umwandeln, indem man ein neues Startsymbol einführt.
Unser prof hat einfach mal die wichtige information übersprungen dass A -> BC oder A -> a... kein wunder das ich das solange nicht gecheckt habe :')
THemen: Aufzählbarkeit, Satz von Rice
müsste es bei 7:40 nicht ein S -> B sein? Ich hätte gedacht, die Nichtterminale dürfen nur einmal in der rechten Seite vorkommen.
Meinst Du "... die *Terminale* dürfen nur einmal in der rechten Seite vorkommen."?
Dem ist nicht so. Die einzigen Einschränkungen sind die Form der Regeln, nämlich ein Nichtterminal auf zwei Nichtterminale (sowas wie A -> BC) oder ein Nichtterminal auf ein Terminal (sowas wie A -> a). Es gibt keine weiteren Einschränkungen, d.h. man kann beliebig viele (aber endlich viele) von diesen Regeln haben und es dürfen sich auch Symbole wiederholen.
@@NLogSpace Okay, gut zu wissen. Danke für die schnelle Antwort!