Let $\Sigma = \{ a,b,c \}$ be an alphabet.

How should I calculate the number of Languages over $\Sigma$?

  • $\begingroup$ Note TeX "\sum" is used for sums (e.g., $\sum_{i=1}^n i$) whereas "\Sigma" should be used for a capital sigma. Also, the entirety of a TeX formula code should be between dollar tags; there's no need for a separate formula for every math symbol you write. See my edits. $\endgroup$
    – dkaeae
    Apr 1 '19 at 9:40
  • $\begingroup$ Hi, thanks for the edits. I will keep that in mind. $\endgroup$
    – rsonx
    Apr 1 '19 at 15:42

It's uncountable infinite.

There are the languages $\{ a^0 \}$, $\{ a^1 \}$, $\{ a^2 \}$, $\{ a^3 \}$ etc., which is already countable infinite.

But the powerset of the integers is uncountable infinite. So for every set S of integers, take the language $\{ a^k: k \in S \}$ and you have an uncountable infinite set.

(The number of languages that can be defined by any algorithm is only countable infinite, so most of these uncountable many languages cannot be described in any way).


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.