Algorithm: Emptiness
• Input: CFG  G = (N, T, P, S);
• Output: YES if L(G) = Æ   NO  if L(G) ¹ Æ
• Method:
• if S is nonterminating then write (’YES’)
          else write (’NO’)
The emptiness problem for CFLs is decidable
Summary:
29/31