Algorithm: Equivalence Problem
• Input: Two minimum state FA, M1and M2
• Output: YES if L(M1) = L(M2)   NO  if L(M1) ¹ L(M2)
• Method:
• if M1 coincides with M2 except for the name of states
   then write (’YES’)
   else write (’NO’)
The equivalence problem for FA is decidable
Summary:
25/26