1
$\begingroup$

This answer says:

We can have uncountable languages only if we allow words of infinite length.

So does that means any (finite / infinite) language or any (finite / infinite) set of languages over any (finite / infinite) alphabet will be uncountable of words have infinite length?

Let me simplify this by asking specifically for the simplest language of infinite length string:

Does the language of "finite" number of words, each of which can be of "infinite length" and are based on "finite" alphabet is uncountable?

Improve this question
$\endgroup$

4 Answers 4

Reset to default
2
$\begingroup$

A finite language is finite. Every finite set is countable, by definition.

A language of finite-length strings over a finite alphabet may be infinite but is always countable.

A language of infinite-length strings over a finite alphabet might be uncountable.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Yes, any finite language is countable. But I am unable to imagine Q1. how we can count strings (show bijection with natural numbers) when they have infinite length. Q2. By last sentence, do you mean to say, infinite length string do not "always" lead to uncountable languages? They may be or may not be countable? Q3. If answer to Q2 is yes, then when will infinite length words lead to countable language? I guess when alphabet is countable OR language is finite then only they lead to countable language. But still I cant imagine how we can count words in them? $\endgroup$
    – Rnj
    Jan 12, 2020 at 17:44
  • 2
    $\begingroup$ @rnj: $\pi$ is an infinite non-repeating decimal; that is, an irrational number which cannot be expressed with any finite stream of digits (in any base). Yet, we have not trouble naming it. A set containing just $\pi$ has one element, and is just as countable as a set containing just 0. All countable means is that there is a homomorphism between the set and the ordinal numbers. $\endgroup$
    – rici
    Jan 12, 2020 at 19:38
2
$\begingroup$

I will answer the question "is there a language which is countable and contains a string of infinite length?"

The answer is yes. Consider the symbols $\{0, 1\}$ and the language consisting of strings which do not contain the symbol $1$. The string of infinitely many $0$s and no $1$s is in the language, but there are still countably many strings in the language (match the empty string with the natural number 0, match the string of infinitely many $0$s with the natural number 1, match the string $0$ with 2, the string $00$ with 3, $000$ with 4, and so on.)

Now, given an infinite string over this set of symbols it is only semi-decidable if the string belongs to this language. That is, there is no TM which will tell you if an infinite string contains no $1$s, but a TM can tell you if a string does contain a $1$.

Since your question seems to indicate that you view the cardinality of a set and the decidability of set membership as being related, you may be interested in apartness relations and, more generally, in constructive mathematics: https://en.wikipedia.org/wiki/Apartness_relation

Improve this answer
$\endgroup$
4
  • $\begingroup$ great point!! Actually this is somewhat related to Q3 in my first comment to rici's answer: when will infinite length words lead to countable language? Is it when alphabet is countable OR language is finite OR both? In your example, alphabet is actually singleton (only 0s). Will it not be countable if we allow both 0 and 1. And what if alphabet is infinitely countable (like set of natural numbers)? $\endgroup$
    – Rnj
    Jan 13, 2020 at 4:51
  • $\begingroup$ In my example the alphabet is $\{ 0, 1\}$, not $\{0\}$. We can modify it and say the string containing infinitely many $1$s and no $0$s is in the language and it is still countable. While the maximum cardinality of a language depends on the alphabet, the minimum cardinality does not (assuming the alphabet is non-empty). For example, the set $\{0\}$ over the natural numbers is a finite language, as is $\{0\}$ over the reals. As to your new question, I do not know how to characterize the countable languages which contain words of infinite length. $\endgroup$
    – Jack
    Jan 13, 2020 at 15:12
  • $\begingroup$ @rnj: I don't believe you can characterize an uncountable language in any way other than that there is no bijection between its elements and the natural numbers, which is tautological. The language of all finite-length strings over a countably infinite alphabet is uncountable, for example, but if you limit the length of the strings, then the result is countable. $\endgroup$
    – rici
    Jan 13, 2020 at 19:21
  • $\begingroup$ And when I say "limit the length of the strings", I include limiting the length of all but a countable number of exceptions. $\endgroup$
    – rici
    Jan 13, 2020 at 19:29
2
$\begingroup$

Take sin x for rational x. We write down the first digit after the decimal point in base 2, the second digit in base 3, third digit in base 4, and so on.

This gives us a countable language of infinite strings over an infinite alphabet.

It has the interesting property that examining any finite number of symbols in an infinite string cannot tell you if it is in the language or not.

Improve this answer
$\endgroup$
0
$\begingroup$

Each infinite word containing ${a,b}$ corresponds (one-one) to a real number with digits of $0,1$ if $a\mapsto 0$ and $b\mapsto 1$. For example, $$ abaaabb\cdots\mapsto 0.0100011\cdots $$ So all strings containing ${a,b}$ has the same infinity as all the numbers in $[0,1]$. And thus language with two symbols of infinite length of words is uncountable.

The infinity of languages with finite or even countable symbols is the same as the one with two symbols. This is a standard theorem in set theory, i.e. $$2^{\aleph_0}=N^{\aleph_0}=\aleph_0^{\aleph_0}={\aleph_1}$$

Improve this answer
$\endgroup$
8
  • $\begingroup$ What if the language only contains one real number? $\endgroup$
    – rici
    Jan 13, 2020 at 19:10
  • $\begingroup$ Yes, if only symbol, the language is countable, i.e. $a, aa, aaa, \cdots$. $\endgroup$
    – hermes
    Jan 13, 2020 at 19:19
  • $\begingroup$ i did not say one symbol. Consider my example where the language contains only the decimal expansion of $\pi$. That's 11 symbols including the decimal point, but the language has only one sentence. $\endgroup$
    – rici
    Jan 13, 2020 at 19:23
  • 1
    $\begingroup$ in formal language theory, a language is any subset of possible sentences from its alphabet. Including the empty set. And including singleton sets. en.wikipedia.org/wiki/Formal_language#Definition $\endgroup$
    – rici
    Jan 13, 2020 at 20:08
  • $\begingroup$ OP asks about general language, and the total number of possible words. It doesn’t concern about formal languages or other types. So do not be too picky about it $\endgroup$
    – hermes
    Jan 13, 2020 at 23:14

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.