I'm currently reviewing my Automata and Languages Theory course and I stumbled upon the following exercise exams. Link

In "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?

  • 1
    $\begingroup$ This is really a question on set theory. I suggest you review set theory first, and then see if you can understand the answer. $\endgroup$ Mar 19 '16 at 10:22

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.


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.