Algorithm: GP Based on CNF
5/10
•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’)