If you want to make money online : Register now

[Solved]: How many languages exist over a finite alphabet?

, , No Comments
Problem Detail: 

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?

Asked By : nmenego

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/54651

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback