•Vstup: G = (N, T, P, S) v CNF, w = a1…an
•Výstup: ANO, pokud w Î L(G)
NE, pokud w Ï L(G)
• Metoda:
• pro každé ai , kde i = 1, …, n:
S[i, i] :=
{A : A ® ai Î P}
• Aplikuj následující pravidlo, dokud žádná z množin S[i, k] nemůže
být změněna:
if A ® BC Î P, B Î S [i, j], C Î S [j+1, k],
kde 1 £ i £ j < k £ n then přidej A do S[i, k]
• if S Î S[1, n] then napiš(’ANO’)
else napiš(’NE’)