Алгоритм. Кока-Янгера-Касами

Вход

• КС-грамматика $G=(\Gamma ,\Sigma ,P,S)$ в нормальной форме Хомского
• Слово $w\in {\Sigma }^{+}$

Выход

• Вывод слова $w$ в грамматике $G$, если $w\in L(G)$ и сообщение об ошибке в противном случае

Алгоритм

Заполнение таблицы

Обозначим $n=|w|$

По сути является алгоритмом динамического программирования. В процессе работы будем заполнять полу-таблицу размерности $n\times n$. Причем строки такой таблицы, полагаем, нумеруются с $0$, а столбцы с $1$

Номер строки i	1	2	$\dots$	n
$0$
$1$
$\dots$
$n-1$

В ячейках таблицы будем записывать множества нетерминалов ${\Gamma }_{i,j},j=1,\dots ,n,i=0,\dots ,n-j$

Заполнение 1 столбца таблицы $j=1$

Нетерминалы ${Г}_{i,1},i=0,\dots ,n-1$ вычисляются следующим образом:

$$X\in {\Gamma }_{i,1}\iff \exists (X\to w_i\in P)$$

где $w_i$ - $i$-ый символ цепочки w

Заполнение 2 столбца таблицы $j=2$

Нетерминалы ${Г}_{i,2},i=0,\dots ,n-2$ вычисляются рекурентно:

$$X\in {\Gamma }_{i,2}\iff \exists (X\to X_1{X}_2\in P),X_1\in {\Gamma }_{i,1},X_2\in {\Gamma }_{i+1,1}$$

Заполнение оставшихся столбцов таблицы $j>2$

Нетерминалы ${Г}_{i,j},j>2$ вычисляются рекурентно:

$$X\in {\Gamma }_{i,j}\iff \exists k,m>0,k+m=j:\exists (X\to X_1{X}_2\in P),X_1\in {\Gamma }_{0,k},X_2\in {\Gamma }_{k,m}$$

Выводы

Слово $w$ принадлежит Языку $L(G)$, если ${\Gamma }_{0,n}=\{S\}$. В противном случае не принадлежит. Алгоритм выбрасывает ошибку

Построение вывода