Algorithm: Finiteness Problem
• Input: DFA  M = (Q, S, R, s, F);
• Output: YES if L(M) is finite    NO  if L(M) is infinite
• Method:
• Let k = card(Q)
• if there exist z Î L(M), k £ |z| < 2k then write (’NO’)
           else write (’YES’)
The finiteness problem for FAs is decidable
Summary:
Note: This algorithm is based on
L(M) is infinite Û there exists z: z Î L(M), k £ |z| < 2k
23/26