Algorithm: Emptiness Problem
• Input: FA  M = (Q, S, R, s, F);
• Output: YES if L(M) = Æ   NO  if L(M) ¹ Æ
• Method:
• if s is nonterminating then write (’YES’)
           else write (’NO’)
The emptiness problem for FAs is decidable
Summary:
22/26