Check if $L$ is regular then $L'$ is regular (and and vice versa)

Question

let's define $w\leftrightarrow v$. It does mean that we may "create" $w$ using word $v$ in following way:
every single letter $x\in \Sigma$ in word $v$ may be replaced by $xx$, and every double letter $xx$ in word $v$ may be replaced by single $x$.
example: $aabbbaaabba\leftrightarrow ababa$
$abbaa\leftrightarrow aaba$
$L'=\{w|w\leftrightarrow v \text{ for some $v\in L$}\}$

And now, check if is true:
(1) $L\in Reg \rightarrow L'\in Reg$ I can show it by construcntion. I consider if exist other way ? Maybe Myhill-Nerode ?
(2) $L'\in Reg \rightarrow L\in Reg$
My Idea
Let's consider equivalent implicaton: $L\notin Reg \rightarrow L'\notin Reg$
It isn't true, due to: $n\ge 0,\ \ L=0^n1^n\notin Reg$; Then $L'=0^*1^*\in Reg$.
So due to the fact that equivalent implications is not true, $L'\in Reg \rightarrow L\in Reg$ is not true. I shown it because I'm not sure the correctness of this. (3) $L\in CFG \rightarrow L'\in CFG$
What about it ?

Answer 1

First of all, let me state your question a little more precisely. Let $A$ be a finite alphabet and let $\sim$ be the congruence on $A^*$ generated by the relations $a \sim a^2$, for each letter $a$. Then if $u = a_1^{k_1}a_2^{k_2} \dotsm a_n^{k_n}$, where $k_1, ..., k_n > 0$ and two consecutive letters $a_i, a_{i+1}$ are always distinct, then $$ [u]_\sim = \{a_1^{r_1}a_2^{r_2} \dotsm a_n^{r_n} \mid r_1, ..., r_n > 0\} $$

Given a language $L$ of $A^*$, let $$ [L]_\sim = \{ u \in A^* \mid \text{there exists $v \in L$ such that $u \sim v$}\}. $$ Let $\mathcal{P}(A^*)$ be the monoid of all languages on $A^*$ under (concatenation) product. Let $\sigma:A^* \to \mathcal{P}(A^*)$ be the monoid morphism defined, for each letter $a \in A$, by $\sigma(a) = a^+$. Thus, for instance, $\sigma(aabacb) = a^+a^+b^+a^+c^+b^+$. Setting $$ \sigma^{-1}(L) = \{ u \in A^* \mid \sigma(u) \cap L \not= \emptyset\} $$ I claim that $$ [L]_\sim = \sigma(\sigma^{-1}(L)) $$ The inclusion $\sigma(\sigma^{-1}(L)) \subset [L]_\sim$ is obvious. For the opposite inclusion, let $v \in [L]_\sim$. Then there exists a word $u$ of $L$ such that $u \sim v$. Thus $v = a_1^{r_1}a_2^{r_2} \dotsm a_n^{r_n}$ and $u = a_1^{k_1}a_2^{k_2} \dotsm a_n^{k_n}$ for some $r_1, ..., r_n > 0$ and $k_1, ..., k_n > 0$. Now $a_1a_2 \dotsm a_n \in \sigma^{-1}(L)$ since the language $\sigma(a_1a_2 \dotsm a_n) = a_1^+a_2^+ \dotsm a_n^+$ contains $u$. Moreover, $v \in \sigma(a_1a_2 \dotsm a_n)$ and thus $v \in \sigma(\sigma^{-1}(L))$.

Now, you can observe that both $\sigma$ and $\sigma^{-1}$ are rational transductions and rational transductions preserve regular languages and context-free languages. It follows that if $L$ is regular, then $[L]_\sim$ is regular and if $L$ is context-free, then $[L]_\sim$ is context-free.