# How many languages exist over the following alphabets?

(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?

• "$|\Sigma| = |\mathbb{N}|$" -- that's clearly wrong. Correct is $|\Sigma^*| = |\mathbb{N}|$. The set of languages is $2^\Sigma$, which is famously uncountably infinite. – 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}$.
• 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}$ ? – thebadboy Sep 10 '18 at 15:26
• @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}|}$. – Daniel Mroz Sep 10 '18 at 15:41