Hlavní rozhodnutelné problémy
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)?
20/26