All we know is that if a language is countable than it must be recognizable. However, a recognizable language may or may not be decidable.
$\begingroup$
$\endgroup$
4
-
3$\begingroup$ $\Sigma^*$, the set of all words, is countable. Therefore, every language is countable. It is certainly not the case that every countable language is recognizable. $\endgroup$ – Shaull Nov 29 '16 at 20:14
-
2$\begingroup$ Every language whose alphabet is finite is countable. Check also this answer: cs.stackexchange.com/a/12665/30527. $\endgroup$ – André Souza Lemos Nov 29 '16 at 21:32
-
1$\begingroup$ @AndréSouzaLemos : Even languages with countably-infinite alphabets are countable. $\endgroup$ – user12859 Nov 29 '16 at 21:52
-
$\begingroup$ @Shaull Make an answer? $\endgroup$ – Yuval Filmus Dec 1 '16 at 16:15
Add a comment
|
$\begingroup$
$\endgroup$
Your premise is incorrect. The set of all words, $\Sigma^*$, is countable (as long as the alphabet is countable, and we usually refer to finite alphabets anyway).
Every language is a subset of $\Sigma^*$, and thus every language is countable. In particular, there are undecidable and unrecognizable languages.
