1
$\begingroup$

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.

  • 0
    Crossposted to [cs.SE](http://cs.stackexchange.com/questions/6907/seeking-alternate-proof-regarding-closure-of-recursively-enumerable-languages).2012-11-26

1 Answers 1

1

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.

  • 0
    I see that [the accepted answer on se.cs by Andrej Bauer](http://cs.stackexchange.com/a/6920/1786) says precisely the same thing I said: "If $A$ is computably enumerable and $f$ is computable then $f(A)$ is computably enumerable."2013-01-24