سوال ۵۱ کنکور ارشد مهندسی کامپیوتر ۱۴۰۰

Fix a finite, non-empty alphabet $\Sigma$. Two cardinality facts settle every option.

Strings $\Sigma^{*}$ are countable. Every string is finite, and $\Sigma^{*}=\bigcup_{k\ge 0}\Sigma^{k}$ is a countable union of finite sets, so $|\Sigma^{*}| = \aleph_0$ (enumerate by length, then lexicographically).

Languages are uncountable. A language is any subset of $\Sigma^{*}$, so the set of all languages is the power set $2^{\Sigma^{*}}$. By Cantor's theorem, $|2^{\Sigma^{*}}| = 2^{\aleph_0} > \aleph_0,$ which is uncountable (the cardinality of the continuum).

Now check each option.

Option 1 — false. Every Turing machine has a finite description (finite state set, finite tape alphabet, finite transition table), so it can be encoded as a finite string. The set of all TM encodings is a subset of a countable set, hence the set of Turing machines is countable.

Option 2 — true. The decidable (recursive) languages are exactly those accepted by a TM that always halts; since TMs are countable, the decidable languages form a countable set. The undecidable languages are $\{\text{all languages}\} \setminus \{\text{decidable languages}\}.$ Subtracting a countable set from an uncountable set still leaves an uncountable set (an uncountable set is not a union of two countable sets). Hence the undecidable languages are uncountable.

Option 3 — false. "All strings over an alphabet" is exactly $\Sigma^{*}$, which is countable, not uncountable.

Option 4 — false. Regular languages are described by finite DFAs / regular expressions, so they form a countable set. Non-regular languages $= \{\text{all languages}\} \setminus \{\text{regular languages}\}$, again uncountable minus countable, so they are uncountable — not countable.

Only option 2 holds.

Exam trick: Anything with a finite description (TMs, DFAs, grammars, decidable languages) forms a countable set; the set of all languages over $\Sigma$ is $2^{\Sigma^{*}}$ and is uncountable. So "most" languages — undecidable, non-regular, non-context-free — are uncountable, because subtracting a countable set from an uncountable one keeps it uncountable.