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.

  • 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$ 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$ Dec 1 '16 at 16:15

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.