I've been viewing the Coursera videos on finite autamata and need some help understanding a question.
What’s the number of non-empty languages that contain only strings of 0's and 1's of length n?
First off do they mean there must be n 0's and n 1's or the combination must be n? For example if n=4 then is 0001 in the language?
I don't understand what is meant by languages? My understanding is a language is the set of all strings that take a DFA from it's start state to an accepted state. I could see the question being how big is the language, but how can you have multiple languages?
The explanation given is
There are $2^n$ strings of 0's and 1's of length n. In a language specified above, each of these strings can show up or not show up. Excluding the empty case, there are $2^{2^n}−1$ such languages.
Also the statement "There are $2^n$ strings of 0's and 1's of length n." is not apparent to me.
They mean that the total length of the string must be exactly $n$. Given an alphabet $\Sigma$, i.e., a set of symbols, a language over $\Sigma$ is simply any set of finite strings of symbols in $\Sigma$. In this problem $\Sigma=\{0,1\}$, and a language is any set of finite strings of zeroes and ones. Restricting yourself to languages recognized by DFAs would limit you to regular languages; the question, however, is about languages in general.
Imagine building a string of $n$ symbols, each of which is $0$ or $1$, one symbol at a time. When you choose the first symbol, there are $2$ possibilities. No matter which choice you make, there are $2$ possibilities for the second symbol, so there are altogether $2\cdot 2$ choices for the first two symbols: $00,01,10$, and $11$. Each time you add another symbol, it can be $0$ or $1$, so you double the number of possibilities. After choosing $3$ symbols, for instance, you can have $000$ or $001$, $010$ or $011$, $100$ or $101$, $110$ or $111$ – a total of $2\cdot 4=8$ strings. Thus, there are
$$\underbrace{2\cdot 2\cdot 2\cdot\ldots\cdot 2}_{n\text{ twos}}=2^n$$
possible strings of length $n$. A language consisting entirely of binary strings of length $n$ must be a subset of this collection of $2^n$ possible strings. A set of $m$ objects has $2^m$ subsets, so this set of $2^n$ strings of length $n$ has $2^{2^n}$ subsets. However, one of these subsets is the empty set, and the question asks for the number of non-empty languages, so we need to subtract one to get the desired number, $2^{2^n}-1$.