[Solved]: How many languages exist with input alphabet {0,1} and all strings in the language have length less than or equal to 5?

Problem Detail: 

I'm trying to write a formal proof in automata theory to show a few properties of DFAs but I am having some trouble with this that I am trying to incorporate into my proof. I want to show how many languages $S$ there are such that $S\subseteq\{0,1\}^*$ and $\forall s\in S, |s|\leq 5$ where $s$ is a string.

I got that there are $2^1+2^2+...+2^5 = 62$ different strings such that $|s|\leq 5$ but that is where I am stuck. How many different languages can I create with $62$ strings? Would it simply be $62!$ ?

Asked By : TheSalamander

Answered By : Rick Decker

First, you seem to have missed the empty string, so there are actually 63 possible strings. In any language, each of the 63 strings could either be in or not in the language, so there will be a total of $2^{63}$ different languages. In the jargon, that's a BFN.

Best Answer from StackOverflow

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