Weiter zum Inhalt

29. Januar 2011

3

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.

Mehr lesen von Studium
3 Kommentare
  1. Jan 29 2011

    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

  2. Abbadon
    Jan 29 2011

    @Felix
    Hi Felix! Müsste doch aber genauso funktionieren, nur steht dann ganz unten keine Startvariable S.

  3. Jan 29 2011

    @Abbadon
    Ja habs grad ausprobiert. Da landet man dann halt mit nem ‚—‚ am Ende

Kommentare wurden geschlossen.