Bijection between $\{0,1\}^*$ and the natural numbers.

Question

So the tasks is to show that $\{0,1\}^*$ is countable.

So the idea that i am having is that each number can be mapped to it's own in decimal.

$f(1001)= 9$

$f(101)=5$

But what happens with all the string which start with zeros.

For example: $f(01001)=$? $f(001001)=$? $f(00000000001001)=$?.

Is my idea completely wrong? Any tips?

Answer 1

Hint: Consider the map $\{0,1\}^* \to \mathbb N$ given by $w \mapsto (1w)_2$.

This assumes that $0 \notin \mathbb N$. If $0 \in \mathbb N$, use $w \mapsto (1w)_2-1$.

Answer 2

You can do this trick. Instead of sending each sequence in $\{0,1\}^\star$ to it's decimal try to first add the digit $1$ at the beginning and then send it to it's decimal (i.e. if you begin with 01 you change it to 101 which is 5 in decimal). That's how you will overcome the zeros problem.