5
$\begingroup$

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!$ ?

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ @DavidRicherby I believe it's a Big F'ing Number. $\endgroup$ – Geobits Oct 7 '15 at 19:41

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.