Algorithm: Finiteness
• Input: CFG  G = (N, T, P, S);
• Output: YES if L(G) is finite    NO  if L(G) is infinite
• Method:
• Let k = 2card(N) 
• if there exist z Î L(M), k £ |z| < 2k then write (’NO’)
           else write (’YES’)
The finiteness problem for CFLs is decidable
Summary:
30/31