HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
alphabetthehowalllanguageswithlengththanequalexist

Problem

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

Solution

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.

Context

StackExchange Computer Science Q#47986, answer score: 7

Revisions (0)

No revisions yet.