CYK-Algorithmus
Habe gerade bei der Suche nach dem CYK-Algorithmus ein Video gefunden, in dem anhand eines Beispiels der CYK-Algorithmus angewandt wird.
Mit dem CYK wird geprüft, ob ein Wort zu einer bestimmten kontextfreien (Typ-2) Sprache gehört. Dies wird auch als das Lösen des Wortproblems für kontextfreie Sprachen bezeichnet. Um den Algorithmus anzuwenden, muss die Grammatik zur gegebenen Sprache in Chomsky-Normalform (CNF) vorliegen.
Beides, die Umwandlung der Grammatik in CNF und die Anwendung des CYK, wird in diesem Video gut verständlich demonstriert.
UPDATE:
Hier gibt es noch eine schöne Java-App zum CYK.
3 Kommentare
Kommentare wurden geschlossen.
Super, vielen Dank.
Das ist wirklich sehr hilfreich. Schade nur, dass er den zweiten Teil der Aufgabe (ein Wort das nicht drin ist) nicht mehr gemacht hat
@Felix
Hi Felix! Müsste doch aber genauso funktionieren, nur steht dann ganz unten keine Startvariable S.
@Abbadon
Ja habs grad ausprobiert. Da landet man dann halt mit nem ‚—‚ am Ende