# If L is regular so is the language of compressed doubles

Suppose L is a regular language over the alphabet $$\Sigma$$. I need to prove that

$$L'=\{x_0\cdots x_n:x_0x_0x_1x_1\cdots x_nx_n\in L, \ \ x_i\in \Sigma\}$$

I thought I could take a DFA which computes L, and take each accepting state, together with the state before it along an edge labeled 0, and the state before that along an edge labeled 0, and make an edge that skips over the middle state. Then do likewise with edges labeled 1.

If you either cut out the middle state or if you leave it and regard the result as an NFA, I can't seem to show that the resulting automaton to computes L'.

• @Addem you will need to do this thing for every state, not only accepting states. Oct 15 at 18:40
• @rici Right, I'll edit to make that clearer. Oct 15 at 19:23
• You can apply an inverse homomorphism. Oct 15 at 19:40 The proof of correctness is now a simple observation on the construction. There is a path $$(q_0,a_1,q_1)(q_1,a_2,q_2)\dots(q_{n-1},a_n,q_n)$$ in the new automaton if and only if there is a 'duplicated path' $$(q_0,a_1,p_1)(p_1,a_1,q_1)(q_1,a_2,p_2)(p_2,a_2,q_2)\dots(q_{n-1},a_n,p_n)(p_n,a_n,q_n)$$ in the original one. For the corresponding languages it is now sufficient to consider 'accepting' paths with initial state $$q_0$$ and accepting state $$q_n$$.
Let $$h\colon \Sigma \to \Sigma^*$$ be the homomorphism given by $$h(\sigma) = \sigma\sigma$$. Then $$L’ = h^{-1}(L)$$. Now use the well-known fact that regular languages are closed under inverse homomorphism.
Equivalently, start with a DFA for $$L$$, and modify the transition function so that whenever the new DFA reads a symbol $$\sigma$$, it simulates the old DFA reading two $$\sigma$$’s in a row.