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)?