Der CYK-Algorithmus (für das Wortproblem kontextfreier Sprachen)

Wir wollen herausfinden, ob eine kontextfreie Grammatik ein bestimmtes Wort akzeptiert, und zwar mit einem möglichst guten Algorithmus. Da kommt der CYK-Algorithmus gerade recht: Er ist so gut, dass er gleich viermal erfunden wurde (von fünf verschiedenen Personen). Außerdem kommt er mit einem attraktiven dreieckigen Tabellenschema und läuft in kubischer Zeit. Was will man mehr?
► Playliste für diesen Videokurs: • Automaten und Sprachen...
► Vorlesungsfolien zum Download: iccl.inf.tu-dr... (12. Vorlesung)
► Aktuelle und frühere Versionen der Vorlesung: iccl.inf.tu-dr...
► Fehler gefunden? Issues melden auf github: github.com/kno...

[@gulsdznl]

Danke sehr! Das Video hat mir sehr geholfen :)

[@FreshKolibri]

18:50-19:25 fehlt der Ton (18:30-19:30 war auch die Kamera eingefroren)

[@prof.markus6569]

Ups, da war der Encoder wohl überlastet. Zum Glück fehlt nichts von Belang. Ich habe am Anfang der nächsten Vorlesung (13. Vorlesung) noch ein weiteres detailliertes Rechenbeispiel für den CYK-Algorithmus zum Selbststudium eingefügt.