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