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'.

  • $\begingroup$ @Addem you will need to do this thing for every state, not only accepting states. $\endgroup$
    – nir shahar
    Oct 15 '21 at 18:40
  • $\begingroup$ @rici Right, I'll edit to make that clearer. $\endgroup$
    – Addem
    Oct 15 '21 at 19:23
  • 1
    $\begingroup$ You can apply an inverse homomorphism. $\endgroup$ Oct 15 '21 at 19:40

When you want to prove your construction correct you have to be precise in your construction. The new automaton has the same states, and the same initial and final states as the original one. Then, as you suggest, for every pair of consecutive edges with the same label in the original automaton, the new automaton will have one edge with that label from the first state to the third one. We cannot delete the middle state, as what is a middle state in one pair of edges might be begin or end state in another.

enter image description here

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.