2
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 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
2
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

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.