Opkt.
Każdą gramatykę postaci
A → a_1….a_ka_{k+1}…a_n
A → a_1
Da sie sprowadzic do:
A → aB
A → bA
A → a
Wyrazenia typu A → B mozna w oczywisty sposob zredukowac.
Teraz przechodzimy do algorytmu:
Tworzymy tablice NxN gdzie N to dlugosc slowa.
Jej pola zdefiniowane sa nastepujaco:
m_{ij}=\{A \in V|A → a_i…a_j\}
m_{ii}=\{A \in V|A → a_i \}
Pola m_{ii} wypelniamy automatycznie a m_{ij} wypelniamy wedlug wzoru:
m_{ij} = a_i m_{i+1,j} \cup m_{i,j-1}a_j
a_im_{i+1,j}=\{A \in V| A → a_iB \land B \in m_{i+1,j}\}
m_{i,j-1}a_j=\{A \in V| A → Ba_j \land B \in m_{i,j-1}\}
Cormen strona 367