•Input: G = (N, T, P, S) in CNF, w = a1…an
•Output: YES if w
Î L(G)
NO if w Ï L(G)
• Method:
• for each ai, i =
1, …, n do
S[i, i] :=
{A : A ® ai Î P}
• Apply
the following rule until no S[i, k] can
be changed:
if A ® BC Î P, B Î S [i, j], C Î S [j+1, k],
where 1 £ i £ j < k £ n then add A to S[i, k]
• if
S Î S[1, n] then write (’YES’)
else write (’NO’)