Cocke-Younger-Kasami-Algorithmus

Der Cocke-Younger-Kasami-Algorithmus (CYK-Algorithmus) i​st ein Algorithmus a​us dem Gebiet d​er theoretischen Informatik. Mit i​hm lässt s​ich feststellen, o​b ein Wort z​u einer bestimmten kontextfreien Sprache gehört. In d​er Fachsprache bezeichnet m​an dies a​ls Lösen d​es Wortproblems für kontextfreie Sprachen. Mit Hilfe v​on Backtracking k​ann der Parse-Tree bzw. d​ie Parse-Trees e​ines gegebenen Wortes d​er Sprache konstruiert werden. Um d​en Algorithmus anzuwenden, m​uss zu d​er vorgegebenen Sprache e​ine Grammatik i​n Chomsky-Normalform vorliegen. Der i​n den 1960er Jahren v​on Itiroo Sakai, John Cocke, Tadao Kasami, Jacob Schwartz u​nd Daniel Younger unabhängig voneinander entwickelte Algorithmus n​utzt das Prinzip d​er dynamischen Programmierung.

Beschreibung

Diese Beschreibung f​olgt Hopcroft/Ullman (1996).

Als Eingabe erhält der Algorithmus eine kontextfreie Grammatik in Chomsky-Normalform und das zu prüfende Wort . Nun wird für jedes Teilwort (d. h.: fängt beim Index an und hat die Länge ) die Menge der Nichtterminale berechnet, die erzeugen, bezeichnet durch .

Gemäß dem Prinzip der dynamischen Programmierung werden erst die für die kleinsten Teilwörter von berechnet, abgespeichert und dann zur somit effizienten Berechnung der nächstgrößeren Teilwörter weiterverwendet. Die kleinsten Teilwörter sind einzelne Buchstaben. Da die kontextfreie Grammatik in Chomsky-Normalform gegeben ist, kann jeder Buchstabe nur in genau einem Schritt von einem Nichtterminal abgeleitet werden.

Ein Nichtterminal einer Grammatik in Chomsky-Normalform kann in einem Schritt nicht auf mehrere Terminale abgeleitet werden. Daher kann ein Teilwort , das mehr als nur ein Zeichen enthält, von nur über eine Regel erzeugt werden. Da Nichtterminale nicht das leere Wort (ε) erzeugen können, muss den linken und den rechten Teil von erzeugen. Daraus folgt:

Mit anderen Worten: kann erzeugen, wenn es gemäß der Produktionsregeln auf abgeleitet werden kann und und wiederum auf und abgeleitet werden, also

.

Das Wortproblem kann nun einfach entschieden werden: kann genau dann von der Grammatik erzeugt werden, wenn gilt. In liegen alle Variablen, die das Teilwort erzeugen können, das beim ersten Buchstaben anfängt und die Länge hat, also das ganze Wort.

Algorithmus

Aus d​er Beschreibung ergibt s​ich folgender Algorithmus:

Für i = 1 ... n
  Für jede Produktion 
    Falls r = 
      Setze 
Für j = 2 ... n
  Für i = 1 ... n - j + 1
    Für k = 1 ... j - 1
      Setze 
Falls , stoppe und gib "w wird von G erzeugt" aus
Stoppe und gib "w wird nicht von G erzeugt" aus

Beispiel

Die Fragestellung lautet, ob sich das Wort durch die Grammatik erzeugen lässt. Die Produktionen der Grammatik seien:

Den Algorithmus kann man mittels einer Tabelle durchführen. Dabei ist in der -ten Spalte und -ten Zeile gespeichert, also die Menge der Nichtterminalsymbole, aus denen sich das Teilwort ableiten lässt, das beim Index anfängt und die Länge hat.

1 2 3 4 5 6
1 {A} {B} {C} {A} {B} {D}
2 {S} {} {} {S} {}
3 {} {} {} {U}
4 {} {} {S}
5 {} {}
6 {S}

Da , lässt sich das gegebene Wort unter der Grammatik aus ableiten.

Eine Linksableitung des Wortes wäre demnach:

=

Also ist ein Wort der Sprache .

Komplexität

Der Algorithmus entscheidet in der Zeit , ob ein Wort der Länge in der Sprache liegt (vgl. Landau-Symbole zur Beschreibung der Notation). Dabei wird Speicherplatz in der Größenordnung benötigt.

Literatur

  • Itiroo Sakai: Syntax in universal translation. In: 1961 International Conference on Machine Translation of Languages and Applied Language Analysis. Her Majesty’s Stationery Office, London 1962, S. 593–608 (mt-archive.info [PDF]).
  • Tadao Kasami: An Efficient Recognition and Syntax-Analysis Algorithm for Context-Free Languages. Air Force Cambridge Research Lab, Bedford 11. Juni 1965 (Scientific report AFCRL-65-758).
  • Daniel H. Younger: Recognition and parsing of context-free languages in time . In: Information and Control. Band 10, Nr. 2, 1967, S. 189–208.
  • John Cocke, Jacob T. Schwartz: Programming languages and their compilers. Preliminary notes. Courant Institute of Mathematical Sciences of New York University, New York 1970.
  • John E. Hopcroft, Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. 3. Auflage. Addison-Wesley, Bonn 1996, S. 148–149 (1. Nachdruck).
  • Dick Grune, Ceriel J. H. Jacobs: Parsing Techniques. A Practical Guide. 1. Auflage. Ellis Horwood, New York 1990, ISBN 0-13-651431-6, S. 81–104 ( [PDF; 1,9 MB]).
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.