Изворни код странице Кук-Јангер-Касами алгоритам

{{Без инлајн извора}}
'''Кук-Јангер-Касами алгоритам''' (''-{Cocke-Younger-Kasami, CYK}-'') је [[алгоритам]] који служи за одређивање припадности неке речи '''-{w}-''' [[контекстно слободном језику]] '''A''' (тип 2 у класификацији Чомског), тј:

:<math>w \in A ?</math>

Овај алгоритам спада у методе [[парсирање|синтаксичке анализе]] које омогућавају анализирање било које [[контекстно слободна граматика|контекстно слободне граматике]]. У основи, овом методом се, почетно од [[Завршни и незавршни симболи|стартног симбола]] граматике, анализирају сва могућа [[извођење|извођења]], док се не утврди да ли реч припада језику или не. Уколико се утврди да припада језику, овај алгоритам омогућава и увид у начин на који је реч изведена.
Стандардни алгоритам анализира КС граматике које су дате у [[Формална граматика|нормалној форми Чомског]]. Ипак, како се свака контекстно слободна граматика може превести у овај облик, метода је применљива на све КСГ.
Постоје и проширења алгоритма којима се могу анализирати граматике које нису у нормалној форми Чомског.

-{CYK}- алгоритам спада у ефикасније алгоритме синтаксичке анализе који имају широку применљивост.
Сложеност алгоритма је полиномска и спада у класу ''-{O(n<sup>3</sup>)}-''(због три угнежђене петље), где је -{n}- дужина анализиране ниске. Наравно, постоје и методе линеарне сложености, али су оне применљиве само на неке поткласе КСГ. Алгоритам припада [[парадигма|парадигми]] [[динамичко програмирање|динамичког програмирања]]. 

== Алгоритам ==
Имплементација динамичким програмирањем:
 <code>
 Улаз: карактери а<sub>1</sub>.... а<sub>n</sub> од којих се састоји задата ниска, симболи задате
 граматике: -{r}- [[Завршни и незавршни симболи|терминала]] и [[Завршни и незавршни симболи|нетерминали]] -{R<sub>1</sub>}- ... -{R<sub>r</sub>}-, где је -{R}-<sub>1</sub> почетни симбол
 Излаз: одговор да ли ниска припада језику граматике
 { локалне варијабле: 
          -{i, j, k}- (бројачке променљиве)
          матрица логичких вредности -{P[n,n,r]}- (на почетку сваки елемент матрице има вредност 0)
          (током рада алгритма -{P[i,j,k]}- ће постати 1 ако подниска улазне ниске од позиције 
          -{i}- на дужини -{j}- може да се генерише из -{R}-<sub>r</sub>) 
   -{for(i = 1; i<= n; i++)}-  (узећемо да је први елемент -{P[1,1,1]}-, а не  -{P[0,0,0]}-) 
      за свако правило граматике -{R<sub>j</sub> → a<sub>i</sub>}- поставити -{P[i,1,j] = 1}-;
   -{for(i = 2; i<= n; i++)}-  (скенира се улазна ниска, а за свако -{a[i]}-)      
     -{for(j = 1; j<= n-i+1; j++)}-  (прегледа се префикс ниске дужине -{ј}-) 
         -{for(k = 1; k<= i-1;k++)}- (извођење из правила граматике)
             за свако правило -{RA -> RB RC}- 
                -{if  ((P[j,k,B]==1) && (P[j+k,i-k,C]==1))  P[j,i,A] = 1;}- 
                  (тј. ако је правило -{RA -> RB RC}- такво да се из -{RB}- може генерисати 
                  подниска дужине -{k}- почев од позиције -{ј}-, и из -{RC}- се може генерисати 
                  подниска дужине -{i-k}- почев од позиције -{j+k}-, онда се из -{RA}- може
                  генерисати подниска дужине -{i}- почев од позиције -{ј}-, тј. -{P[j,i,A] = 1}-)
 
  -{if  (P[1,n,1]==1) print}- 'ниска је члан језика'
  -{else  print}- 'ниска није члан језика'
 }
 </code>

== Модификације алгоритма и примене ==
* Ради конструкције [[Дрво извођења|дрвета извођења]],-{CYK}- алгоритам се може модификовати тако да елементи матрице -{P}- не буду логичке вредности него чворови дрвета извођења. Како граматика може бити вишезначна, неопходно је памтити у матрици заправо листу чворова, а резултат ће бити не само једно дрво, већ читав низ могућих стабала.

* Теоретски значај -{CYK}- алгоритма лежи у могућности да се користи као конструктиван доказ да је проблем припадности КСЈ одлучив.

* Ради синтаксичке анализе стохастичких КСГ(СКСГ), -{CYK}- алгоритам се може модификовати тако да елементи матрице -{P}- не буду логичке вредности, већ вероватноће. СКСГ су КСГ у којима се свака примена правила обавља уз неку вероватноћу; тачније, вероватноћа извођења је производ вероватноћа правила која се користе у тим извођењима. СКСГ се користе у области -{NLP}- (обрада природних језика) и проучавања -{[[RNK]]}- молекула у [[биоинформатика|биоинформатици]].

== Види још ==
* [[Ерлијев анализатор|Ерлијев алгоритам]]

== Литература ==
{{Литература|2}}
* ''Скрипта за предмет „Информатика 3“, УНИ Карлсруе, Петер Сандерс''
* {{Cite book |ref= harv|last= Витас|first= Душко М.|authorlink= Душко Витас|coauthors= |title= Преводиоци и интерпретатори (Увод у теорију и методе компилације програмских језика)|year= 2006|url= |publisher= Математички факултет|location= Београд|id=}}

{{Литература крај}}

== Спољашње везе ==
* [http://www.matf.bg.ac.rs/~jelenagr/ASP/v22.htm -{CYK}- алгоритам], простор Јелене Грмуше, МатФ

{{нормативна контрола}}

[[Категорија:Алгоритми]]
[[Категорија:Преводиоци (рачунарство)]]