Algorithm: Membership
• Input: CFG  G = (N, T, P, S) in Chomsky       normal form; w Î T+
• Output: YES if w Î L(G)  
NO  if w Ï L(G)
• Method I:
• if S Þn w, where 1 £ n £ 2|w| – 1, then write (’YES’)
            else  write (’NO’)
• Method II:
• See: The general parsing method based on CNF
The membership problem for CFLs is decidable
Summary:
26/31