Main Decidable Problems
1. Membership problem:
• Instance: FA M, w Î S*; Question: w Î L(M)?
2. Emptiness problem:
• Instance: FA M; Question: L(M) = Æ?
3. Finiteness problem:
• Instance: FA M; Question: Is L(M) finite?
4. Equivalence problem:
• Instance: FA M1, M2; Question: L(M1) = L(M2)?
20/26