CFG in Chomsky-Normalform überführen
Вставка
- Опубліковано 15 чер 2013
- inkl. Entfernung von Zyklen.
Neue Videoreihe:
Algorithmus 1:
• CFG zu Chomsky-Normalf... 1. ε-Produktionen entfernen
• CFG zu Chomsky-Normalf... 2. Kettenregeln entfernen
• CFG zu Chomsky-Normalf... 3. unnütze Symbole entfernen
• CFG zu Chomsky-Normalf... 4. Terminale durch Nichtterminale ersetzen
• CFG zu Chomsky-Normalf... 5. Binarisieren
Algorithmus 2:
• CFG zu Chomsky-Normalf... 1. nicht erzeugende Variablen entfernen
• CFG zu Chomsky-Normalf... 2. nicht erreichbare Variablen entfernen
• CFG zu Chomsky-Normalf... 3. Variablen und Terminale trennen
• CFG zu Chomsky-Normalf... 4. rechte Regelseiten kürzen
• CFG zu Chomsky-Normalf... 5. ε-Produktionen entfernen
• CFG zu Chomsky-Normalf... 6. Kettenregeln entfernen
• CFG zu Chomsky-Normalf... 7. leeres Wort wieder hinzufügen
Quelle:
Hopcroft, John E. ; Motwani, Rajeev ; Ullman, Jeffrey D.: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. 2. Aufl. München [u.a.] : Pearson Studium, 2002 (Informatik). -- ISBN 3-8273-7020-5, S. 311ff.
Vielen Dank für die super Videos. Haben mir sehr beim Verständnis von Grammatiken, Sprachen und Automaten geholfen :)
Super erklärt, vielen Dank!
Danke, war hilfreich! Wird mir hoffentlich in der Klausur morgen helfen :D
Dankeschön! Super erklärt, sofort verstanden, rettet meine Theo Inf Klausur :D
Gibt es noch ein anderes Video von dir, indem du erklärst, wie man den „Zyklus“ auflöst? Gibt es einen bestimmten Begriff für diesen Fall mit dem Zyklus? Hätte gerne mehr Input. Danke
Danke für dein Interesse. In dem verlinkten Video über Kettenregeln erkläre ich es auch nochmal: ua-cam.com/video/pzlL-ZwGUJY/v-deo.html
Im Hopcroft nennen sie es auch "zirkuläre Einheitsproduktionen".
Hilft mir gut weiter
What if you have more than 2 symbols on the left side of a production rule?
Then you have a grammar that is more expressive than a CFG.
Right. Stupid question. But thank you for the quick reply.
No, it's not! Didn't you ever wonder why there is always just one symbol on the left side? Yes, you can have more and you can even have terminals on the left side. There is so much more than CFG. It's a valid question. You can question everything and it will make you smarter, so just do it. :)
grottig erklärt no front
Danke für die Rückmeldung. Ich habe eine Serie produziert, wo ich jeden Schritt einzeln erkläre, aber als ich dieses Video hier runtergenommen habe, hat die anderen keiner geguckt. 😅 Wenn dir dieses Video nicht geholfen hat, kann ich zumindest auf die Videoreihe verweisen, die in der Beschreibung verlinkt ist.
Toll, das du in diesem Video erklärst, wie man Zyklen auflöst. Das wird nämlich sonst fast nirgends erwähnt, obwohl es wahrscheinlich eine typische Klausuraufgabe wäre.
Das sollte vielleicht im Titel stehen, damit man Bescheid weiß, wenn man danach sucht.
+SomethingScanning Danke, das ist ja ... unglaublich. Ich hab es in die Videobeschreibung geschrieben. Die Titelleiste ist zu kurz für alle wichtigen Informationen. :(
Studierst du noch?
Wenn ja: Hast du angefangen zu rauchen?
She sounds so cute^^
wieso geht am Ende Z->AY? das passt überhaupt nicht.
Ich hab am Anfang S->aaY. Die as ersetze ich mit Hilfe von A->a und erhalte S->AAY. Das will ich binarisieren und kann entweder AA oder AY zu einem Nichtterminalen zusammenfassen und ich hab mich entschieden, AY durch Z zu ersetzen und das Z zu AY expandieren zu lassen. Ich schreibe also S->AZ und Z->AY.
WIe alt bist du? Warst du zum Zeitpunkt des drehs?
+Valansch Da war ich 23. Ja, ich weiß, ich höre mich an wie ein kleiner Junge. ^^
***** :D
Hi. Ich habe vor mich ein bisschen in die Thematik einzulesen. Ich bin totaler Amateur und habe davon keine Ahnung. Kannst du mir Literatur empfehlen, die einen leichten Einstieg bietet? Btw: werde mir natürlich zusätzlich Videos von dir anschauen.
Hallo. Ich kenne leider kein ultimatives Buch für den Einstieg. Der Socher, den ich oft zitiere, ist sehr leicht zu verstehen, aber voller Fehler. Hopcroft, ebenfalls oft von mir zitiert, sind schwieriger zu verstehen, aber das ist ein Standardwerk, in dem alles drin steht. Mehr Bücher hab ich darüber nicht gelesen. :) Wie wäre es, wenn du in eine Fachbibliothek gehst, in ein paar Bücher reinblätterst und das nimmst, was dir am einfachsten erscheint?
***** gute Idee. Also ich habe Ahnung von Quantenfeldtheorie etc. (bin in der theoretischen Physik). Deswegen glaube ich schon, dass ich mich da gut eindenken kann. Das ist zwar eine ganz andere Baustelle, aber ich bin ich mit abstrakten Konzepten vertraut. Die Denkweise ist eventuell ähnlich (auch wenn ich das als nicht-Linguist nicht gut beeurteilen kann). Bin jetzt eher über Umwege darauf gekommen, weil ich schon seid längerer Zeit ein großer Chomsky Fan bin und schon immer mal wissen wollte, was der Herr so macht, wenn er sich nicht gerade mit politischen Analysen befasst.