TransWikia.com

Is there a way to map the concatenation operation over strings to the addition operation over $mathbb{N}$

Computer Science Asked on October 21, 2021

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

One Answer

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.

Answered by user114966 on October 21, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP