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$)


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$ – Dmitry Jul 18 '20 at 20:19
  • $\begingroup$ It became even simpler) $\endgroup$ – Dmitry Jul 18 '20 at 20:24

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.