برای هر یک از زبان‌های زیر (با استدلال) مشخص کنید جزء کدام یک از رده‌های زیر قرار می‌گیرند و جزء کدام رده‌ها قرار نمی‌گیرند. معمولاً برای هر زبان استدلال در مورد دو رده دارای اهمیت است.

رده‌ها:

1. منظم ‎(Regular)‎
2. مستقل از متن ‎(Context-free)‎
3. تصمیم‌پذیر ‎(Decidable)‎
4. تشخیص‌پذیر/شمارش‌پذیر ‎(Recognizable/Enumerable)‎
5. متمم‌تشخیص‌پذیر ‎(Co-Recognizable)‎

زبان‌ها:

1. ‎$LEAST_{100} = \left\{\left<M\right> | M \mbox{ is a Turing machine and }L(M)\mbox{ has at least 100 elements} \right\}$‎
2. ‎$MOST_{100} = \left\{\left<M\right> | M \mbox{ is a Turing machine and }L(M)\mbox{ has at most 100 elements} \right\}$‎
3. ‎$HALT_{10000} = \left\{\left<M\right> | M \mbox{ is a Turing machine that halts on any input and } \left|\left<M\right>\right| \leq10000 \right\}$‎
4. ‎$ MIN = \left\{a^m.b^n.c^k | k \geq \min(m‎, ‎n) \right\} $‎

• سوال قبل