I'm currently reviewing my Automata and Languages Theory course and I stumbled upon the following exercise exams.LinkIn Exercises for ACS 1, Fall 2004, sheet 1, exercise 1 item C, the question is,How many languages exist over the symbol sets from (a)?Question (a) describes the alphabets $S=\{a,b\}$ and $S=\{1\}$. The answer to the question as provided in the same link is In both cases, $|^*| = \mathbb N$, that is, there are $2^{\mathbb N}$ many languages over these alphabets  indeed, over any finite alphabet there are $2^{\mathbb{N}}$ languages.Here $\mathbb{N}$ is the set of all natural numbers. I am confused as to how the author came to this conclusion.Update:In my understanding, since {a,b} is a set of strings of {a,b}, it follows that it is a subset of {a,b}* or the set of all strings over {a,b}. So, as per set theory, the cardinality of a set containing the subsets of all strings over {a,b} = powerSet({a,b}*) whose cardinality is equal to $2^{\mathbb{N}}$. Is my understanding correct?
How many languages exist over a finite alphabet?
formal languages;automata;finite automata
The number of possible words is countably infinite, since we can list them in increasing order of length:$$\epsilon,a,b,aa,ab,ba,bb,\ldots \\\epsilon,1,11,111,1111,11111,\ldots$$This is why $|\Sigma^*| = \aleph_0$ (to use a more common notation). The set of all possible languages is the set of all subsets of $\Sigma^*$ (known also as the power set of $\Sigma^*$), which by definition has cardinality $2^{\aleph_0} = \aleph$.If you are unfamiliar with these terms, you need to do some reading on elementary set theory.