(a) We have alphabet $\Sigma=\lbrace 1 \rbrace$, $\Sigma=\lbrace a,b \rbrace$ and (b) also an alphabet with size $k$ and words with length $n$.

For the first two alphabets in (a), we know that there are countably infinite words: $$|\Sigma| = |\mathbb{N}|$$

For the alphabet in (b) we know we have $k^n$ number of words.

Now I need to find the number of languages that exist for the symbol set $(a)$ and $(b)$.

I think the number of alphabets is also countably infinite, so it has the same size as the power set of $\Sigma$ which has a cardinality $|\Sigma| = |\mathbb{N}|$, therefore there are $2^{|\mathbb{ℕ}|}$ languages.

Now my question is, does this $k^n$ have a role in this $2^{|\mathbb{ℕ}|}$; does it change anything?

  • $\begingroup$ "$|\Sigma| = |\mathbb{N}|$" -- that's clearly wrong. Correct is $|\Sigma^*| = |\mathbb{N}|$. The set of languages is $2^\Sigma$, which is famously uncountably infinite. $\endgroup$ – Raphael Nov 9 '18 at 18:30

A language over an alphabet $\Sigma$ is any subset of the set of all finite strings with elements in $\Sigma$. If $\Sigma$ is finite or countably infinite, and not empty, then the set of all finite strings with elements in $\Sigma$ is countably infinite ($\aleph_0$) and the set of all languages over the alphabet $\Sigma$ has the same cardinality as the real numbers ($\aleph_1$). (Not calling it just "uncountable", because the set of languages is indeed uncountable, but there are uncountable sets with higher cardinality).


A language over a set of words $S$ is just a subset of $S$. So the total number of such languages is $|P(S)| = 2^{|S|}$.

If we take $S$ to be $\{0\}^*$ then indeed $|S| = |\mathbb{N}|$, and the total number of languages is $2^{|\mathbb{N}|}$. The same goes for $S = \{a,b\}^*$.

If $S$ is the set of all words of length $n$ over an alphabet of size $k$, then $S$ has $k^n$ elements. So the number of languages over $S$ is $2^{k^n}$.

  • $\begingroup$ Okay but if I want to know the number of languages of both (1 value for both), does that mean the the total is : $2^{|\mathbb{N}|}$ + $2^{k^n}$ ? $\endgroup$ – thebadboy Sep 10 '18 at 15:26
  • $\begingroup$ @thebadboy OK, I misunderstood the question. In that case the total number is indeed $2^{|\mathbb{N}|} + 2^{k^n}$, which is equal to $2^{|\mathbb{N}|} $. $\endgroup$ – Daniel Mroz Sep 10 '18 at 15:41
  • 1
    $\begingroup$ What is "A language over a set of words"? $\endgroup$ – David Richerby Sep 10 '18 at 15:51

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.