Algorithm: Membership Problem
• Input: DFA  M = (Q, S, R, s, F); w Î S*
• Output: YES if w Î L(M)  
NO  if w Ï L(M)
• Method:
• if sw |–* f,  f Î F then write (’YES’)
      else write (’NO’)
The membership problem for FAs is decidable
Summary:
21/26