So I would like to show that the class of Recursively Enumerable languages are closed under the shrink operation. In other words, $\mathrm{shrink}_a(L) = \{x \mid x=\mathrm{shrink}_a(w), w\in L\}$ and where $\mathrm{shrink}_a(w)$ is the string formed from $w$ by replacing every maximal substring of two or more a's by a single a. For example, $\mathrm{shrink}_a(baaab) = bab$.
So I was browsing around for other examples to study, and I came across the following proof for the $\mathrm{prefix}$ operation: https://cs.stackexchange.com/questions/1731/proving-that-recursively-enumerable-languages-are-closed-against-taking-prefixes (the proof given by the user Wu Yin). I thought that this was a very cool way of proving something like this, instead of just directly building an alternate TM. I'm curious to know, can anyone come up with a proof that is of a similar style and flavor to the one pointed above? I would be very curious to see a similar bijective proof regarding countable/uncountable sets!
This has reminded me that there can be many ways to prove something, so I wanted to see what kind of flavor other people's proofs might have to this sample problem. I find that too often, students (and myself included) get caught up in a single procedure for finding solutions to a particular type of problem and neglect to see other ways of showing the same result.
Isn't it clear that the image of an RE language $\def\L{\mathscr L}\L$ under any computable operation $f$ on its elements is also RE? Because by hypothesis, there was a machine $M_\L$ which enumerated the elements of $\L$, and so one can easily build a machine which uses $M_\L$ as a subroutine, and which, for each string $s$ output by $M_\L$, transforms $s$ to $f(s)$ and outputs that instead.
Since $shrink_a$ is just such a computable function $f$, it follows that $shrink_a(\L)$ is RE whenever $\L$ is.