If an alphabet $= \{a, b\}$

I believe an example of a finite language over that alphabet with positive cardinality would be the set equal to $(a+b)^4$

An example of a countably infinite language over the alphabet would be ${a}^*$

But do uncountably infinite languages even exist? Each item (string) of the language is finite, so I believe you could make a one-to-one relationship with the set of integers.

  • 1
    $\begingroup$ Of course, there is also a difference between the language and the underlying alphabet. The alphabet $\{0,1\}$ is finite; the language $\{0,1\}^\omega$ of infinite sequences from that alphabet is an uncountably infinite language. $\endgroup$ – Carl Mummert May 22 '18 at 18:00
  • $\begingroup$ @Carl: Can you maybe give this a better set of tags? I feel like the proper tags would provide a lot more context. $\endgroup$ – Asaf Karagila May 22 '18 at 18:08
  • $\begingroup$ (modified from a comment in Asaf Karagila's recently deleted answer) Regarding uncountably infinite languages, see my answer to How to write an individual real number? in the Mathematics Educators Stack Exchange. $\endgroup$ – Dave L. Renfro May 22 '18 at 18:09
  • $\begingroup$ @Dave: I believe that the question is not about that kind of languages, which is why I deleted my answer. $\endgroup$ – Asaf Karagila May 22 '18 at 18:12
  • $\begingroup$ @Asaf Karagila: I understand, but I think few people outside of logician types are even aware of the existence of such things, and thus our contributions (in my opinion) may be of use for future visitors to this question. I only know about this (in a layman's sense) because Dickmann's 1975 book Large Infinitary Languages was on the library shelves when I went away to college (in 1977), and I was fascinated by the fact that people actually could study something like this (although I've seen so much since then that it's no longer THAT fascination to me). $\endgroup$ – Dave L. Renfro May 22 '18 at 18:38

In elementary computability theory, we usually work with languages that are subsets of $\mathbb{N}$, or which are in bijection with subsets of $\mathbb{N}$, such as languages consisting of finite words over a finite alphabet.

In more advanced levels of computability theory we also look at more general collections, such as collections whose elements are infinite sequences from a finite or countable alphabet. Like countable languages, we can use Turing machines to define what it means for one of these uncountable "languages" to be decidable, semidecidable, etc. The more general analogy is via the arithmetical hierarchy. This allows us to make similar definitions for subsets of $\mathbb{N}$, subsets of $\mathbb{2}^\mathbb{N}$, and subsets of $\mathbb{N}^\mathbb{N}$.

However, it may may not be very common to call these uncountable collections "languages". For example, we are often interested in a "language" consisting of all infinite paths through some computable subtree of the complete binary tree. Rather than calling these "languages", we typically call them "$\Pi^0_1$ classes".


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.