1. Problém členství:
• Instance: FA M, w Î S*; Otázka: w Î L(M)?
2. Problém
prázdnosti:
• Instance: FA M; Otázka: L(M) = Æ?
3. Problém
konečnosti:
• Instance: FA M;
Otázka: Je L(M) konečný?
4. Problém
ekvivalence:
• Instance: FA M1, M2;
Otázka: L(M1) = L(M2)?