Weiter zum Inhalt

Beiträge mit Stichwort ‘CYK’

29
Jan

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.