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$)
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
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP