1
$\begingroup$

... In the context of the question:

Say we have a set $S$, that contains all the strings with the alphabet $a$ and $b$, i.e. $$S = \left\{a, b, aa, bb, ab, ba, aaa, bab, bba, \dots\right\}$$

Now, say we have a function $R(t)$ that replaces the leftmost occurrence of $a$ in $t$ with $b$, i.e. $R(aaabb) = baabb$, and $R(bbaaaab) = bbbaaab$, and so on.

How do we prove that $R$ is injective, or otherwise?

$\endgroup$
2
  • 6
    $\begingroup$ I think it isn't injective. Because $R(a)=b$ and $R(b)=b$... $\endgroup$ Oct 28, 2018 at 2:21
  • 1
    $\begingroup$ @DoyunNam, thank you; that was short and sweet. $\endgroup$
    – SRSR333
    Oct 28, 2018 at 3:04

1 Answer 1

3
$\begingroup$

It is not injective. Take $s_1 = ab$ and $s_2 = bb$. Then, $R(s_1) = bb = R(s_2) = bb$. But, $s_1 \ne s_2$. So, we have one output mapping to two inputs. This is just a more exhaustive explanation of Doyun's answer.

$\endgroup$
1
  • $\begingroup$ Thanks very much for the explanation. $\endgroup$
    – SRSR333
    Oct 28, 2018 at 3:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .