Given an alphabet, say $\Sigma = \{0,1\}$, I can make a one-to-one mapping from all possible strings $x \in \Sigma^*$ to $\mathbb{N}$. This could be done by ordering $\Sigma^*$ lexicographically and assigning the $i$th string $x_i$ to number $i \in \mathbb{N}$.

But given strings $x_i,x_j \in \Sigma^*$, is there any special mapping such that the concatenation operation $f:\Sigma^* \rightarrow \Sigma^* | (x_i,x_j) \rightarrow x_ix_j$ is also related to the usual addition performed over the corresponding indices $i,j \in \mathbb{N}$ to which $x_i$ and $x_j$ are mapped ?

For instance, if I assign the character $\{1\}$ to the number $1$, and string $x$ is assigned the number $10$, is there a mapping such that the string $x1$ is assigned the number $11$ ? (i.e. $10 + 1$)


1 Answer 1


Yes, if you don't want an injective mapping: just assign to all strings value 0.

No, if you want an injective mapping:

  • Empty string must correspond to value $0$. Otherwise, $$value(\epsilon) = value(\epsilon \cdot \epsilon) = 2 value(\epsilon),$$ - contradiction when $value(\epsilon)\ne 0$.

  • Let "0" correspond to value $a$ and "1" correspond to value $b$ ($a,b > 0$). Then
    $$value(0^b) = b \cdot value(0) = ab = a \cdot value(1) = value(1^a)$$ - contradiction, since both $0^b$ and $1^a$ correspond to the same value.

  • $\begingroup$ Thanks for the comment! My mistake, I've never used "one-to-one" when talking about functions, and I decided that it means "bijective" without checking it. Let me fix it. $\endgroup$
    – user114966
    Commented Jul 18, 2020 at 20:19
  • $\begingroup$ It became even simpler) $\endgroup$
    – user114966
    Commented Jul 18, 2020 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.