CYK

CYK

Der Cocke-Younger-Kasami-Algorithmus (CYK-Algorithmus) ist ein Algorithmus aus dem Gebiet der Theoretischen Informatik. Mit ihm lässt sich feststellen, ob ein Wort zu einer bestimmten kontextfreien Sprache gehört. In der Fachsprache bezeichnet man dies als Lösen des Wortproblems für kontextfreie Sprachen. Mit Hilfe von Backtracking kann der Parse-Tree bzw. die Parse-Trees eines gegebenen Wortes der Sprache konstruiert werden. Um den Algorithmus anzuwenden, muss zu der vorgegebenen Sprache eine Grammatik in Chomsky-Normalform vorliegen. Der Ende der 1960er Jahre von John Cocke, Tadao Kasami, Jacob Schwartz und Daniel Younger unabhängig voneinander entwickelte Algorithmus nutzt das Prinzip der dynamischen Programmierung.

Inhaltsverzeichnis

Beschreibung

Als Eingabe erhält der Algorithmus eine kontextfreie Grammatik G = (N,T,P,S) in Chomsky-Normalform und das zu prüfende Wort w = w_1w_2\ldots w_n \in T^*. Nun wird für jedes Teilwort w_{i,j} := w_i\ldots w_j die Menge der Nichtterminale berechnet, die wi,j erzeugen, bezeichnet durch Vi,j.

Gemäß dem Prinzip der dynamischen Programmierung werden erst die Vi,j für die kleinsten Teilwörter von w 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 wi,j, das mehr als nur ein Zeichen enthält, von A nur über eine Regel (A \rightarrow BC) \in P erzeugt werden. Da Nichtterminale nicht das Leere Wort (ε) erzeugen können, muss B den linken und C den rechten Teil von wi,j erzeugen. Daraus folgt:

A \in V_{i,j} \Leftrightarrow \exists k \in \mathbb{N}, i \le k \le j - 1: (A \rightarrow BC) \in P \and B \in V_{i,k} \and C \in V_{k + 1, j}

Mit anderen Worten: A kann wi,j erzeugen, wenn es gemäß der Produktionsregeln auf BC abgeleitet werden kann und B und C wiederum auf wi,k und wk + 1,j abgeleitet werden, also A \rightarrow BC \rightarrow w_i\ldots w_kC \rightarrow w_i\ldots w_kw_{k+1}\ldots w_j = w_{i,j}.

Das Wortproblem kann nun einfach entschieden werden: w kann genau dann von der Grammatik erzeugt werden, wenn S\in V_{1,n} gilt. In V1,n liegen alle Variablen, die das Teilwort vom ersten bis zum letzten Buchstaben erzeugen kann, also das ganze Wort.

Algorithmus

Aus der Beschreibung ergibt sich folgender Algorithmus:

Für i = 1 ... n
  Für jede Produktion (l \rightarrow r) \in P
    Falls r = wi
      Setze V_{i,i}:=V_{i,i} \cup \{ l \}
Für j = 2 ... n
  Für i = j-1 ... 1
    Für k = i ... j - 1
      Für jede Produktion (l \rightarrow BC) \in P
        Falls B \in V_{i,k} und C \in V_{k + 1,j}
          Setze V_{i,j}:=V_{i,j} \cup \{ l \}
Falls S \in V_{1,n}, 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 w, w = bbabaa durch die Grammatik G = ({S,A,B,C},{a,b},P,S) erzeugen lässt. Die Produktionen P der Grammatik seien:

S \rightarrow AB \mid BC
A \rightarrow BA \mid a
B \rightarrow CC \mid b
C \rightarrow AB \mid a

Den Algorithmus kann man mittels einer Tabelle durchführen. Dabei ist in der i-ten Zeile und j-ten Spalte Vi,j gespeichert, also die Menge der Nichtterminalsymbole aus denen sich das Teilwort w_ i \dots w_{j} ableiten lässt.

Vi,j 1 2 3 4 5 6
1 {B} {} {A} {S,C} {B} {A,S}
2 {B} {S,A} {S,C} {B} {A,S}
3 {A,C} {S,C} {B} {S,A}
4 {B} {A,S} {}
5 {A,C} {B}
6 {A,C}

Da S\in V_{1,6}, lässt sich das gegebene Wort w = bbabaa unter der Grammatik G aus S ableiten. Also ist w ein Wort der Sprache L(G).

Komplexität

Der Algorithmus entscheidet in der Zeit \mathcal{O}(n^3 \cdot \left|P\right|), ob ein Wort der Länge n in der in Chomsky-Normalform gegebenen Sprache L liegt. \left|P\right| bezeichnet hier die Größe der Produktionen. Da die Grammatik in Chomsky-Normalform ist, gilt \#\mbox{Produktionsregeln} = \Theta(\left|P\right|). Mit p=\#\mbox{Produktionsregeln} ergibt sich eine Zeitkomplexität von \mathcal{O}(n^3 \cdot p). Dabei wird Speicherplatz in der Größenordnung \mathcal{O}(n^2 \cdot \left|P\right|) = \mathcal{O}(n^2 \cdot p) benötigt.

Literatur

  • Takao Kasami: An efficient recognition and syntax-analysis algorithm for context-free languages. In: Scientific report AFCRL-65-758. Air Force Cambridge Research Lab, Bedford 1965. 
  • Daniel H. Younger: Recognition and parsing of context-free languages in time n3. In: Information and Control. 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. 
  • Grune, Dick; Jacobs, Ceriel J. H.: Parsing Techniques: A Practical Guide. 1. Auflage. Ellis Horwood, New York 1990, ISBN 0-13-651431-6, S. 81-104 (PDF, 1.9 MB). 

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем написать курсовую

Schlagen Sie auch in anderen Wörterbüchern nach:

  • cyk — {{/stl 13}}{{stl 8}}wykrz. {{/stl 8}}{{stl 20}} {{/stl 20}}{{stl 12}}1. {{/stl 12}}{{stl 7}} wyraz, zwykle powtarzany kilka razy, oddający urywany, trzeszczący odgłos wydawany przez niektóre owady (np. świerszcze, koniki polne) . {{/stl 7}}{{stl… …   Langenscheidt Polski wyjaśnień

  • Cyk — or CYK may refer to: CYK algorithm, a grammar related algorithm Cyk, Greater Poland Voivodeship (west central Poland) Cyk, Masovian Voivodeship (east central Poland) Çük, a Tatar holiday This disambiguation page lists articles associated with the …   Wikipedia

  • CYK — Algorithme de Cocke Younger Kasami L algorithme de Cocke Younger Kasami permet de déterminer si une phrase peut être générée par une grammaire non contextuelle, et si oui, de quelle manière. L algorithme permet d obtenir l arbre syntaxique de la… …   Wikipédia en Français

  • Cyk — Algorithme de Cocke Younger Kasami L algorithme de Cocke Younger Kasami permet de déterminer si une phrase peut être générée par une grammaire non contextuelle, et si oui, de quelle manière. L algorithme permet d obtenir l arbre syntaxique de la… …   Wikipédia en Français

  • cyk — 1. «wyraz naśladujący odgłos chodzącego zegara» 2. «wyraz naśladujący suchy, trzeszczący szmer wydawany przez konika polnego, świerszcza itp.» 3. «wyraz określający zrobienie czegoś w sposób bardzo szybki» 4. pot. «wyraz wypowiadany przy… …   Słownik języka polskiego

  • CYK-алгоритм — Связать? CYK алгоритм (англ. CYK algorithm) алгоритм, применяемый в области теоретической информатики, позволяющий установить, принадлежит ли слово некоторой определенной контекстно свободной грамматике …   Википедия

  • CYK algorithm — The Cocke–Younger–Kasami (CYK) algorithm (alternatively called CKY) is a parsing algorithm for context free grammars. It employs bottom up parsing and dynamic programming. The standard version of CYK operates only on context free grammars given… …   Wikipedia

  • Cyk, Greater Poland Voivodeship — For other places with the same name, see Cyk. Cyk   Village   …   Wikipedia

  • Cyk, Masovian Voivodeship — For other places with the same name, see Cyk (disambiguation). Cyk   Village   Country Poland Voi …   Wikipedia

  • CYK-Algorithmus — Der Cocke Younger Kasami Algorithmus (CYK Algorithmus) ist ein Algorithmus aus dem Gebiet der Theoretischen Informatik. Mit ihm lässt sich feststellen, ob ein Wort zu einer bestimmten kontextfreien Sprache gehört. In der Fachsprache bezeichnet… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”