# Prove that Doubling operation on a language has an automata associated?

Let be the operation $Double$ on the words on an $\Sigma$ alphabet which inserts after each character a copy of this character. Thus, $D(ab) = aabb$, $D(abaab) = aabbaaaabb$, etc... We had to prove that these regular expressions are closed by this operation and it was a sucess.

We now have to prove this properties for automata. In other words, we have to prove that if we have a language $L$ such that it exists an automata $A$ that recognize $(L=L(A))$, there also exists an automata $A'$ that recognize that language $Double(L)$.

I shouldn't use equivalence between automatas and regular expressions

## Proof attempt

Following Rick Decker's advises, here is the second attempt to prove that if we have a language $L$ such that it exists an automata $A$ that recognize $(L=L(A))$, there also exists an automata $A'$ that recognize tha language $Double(L)$ :

To prove it, we are goint to construct an automata $A'$ such that $A'=D(L)$.

The idea is to construct an input string of $w$ that we reads from left to right. After having read the entire string $w$, it checks whether the following char is the same. If it is the case we remain in the final state. Otherwise, we go to a transitional state and if the following char isn't exactly the same, we go to the bin state.

1. $Q=\{q_0, q_1, q_2, p\}$, $q_1,q_2$ are waiting states, $p$ is a bin state.
1. $\Sigma$ is the alphabet. For the example it is : $\{a,b\}$.
1. $\delta : Q × \Sigma → Q$ is a function, called the transition function,

$$\begin{array}{c|cc|c|c|} & a & b\\ \hline q_0 & q_2 & q_1\\ q_1 & p& q_0\\ q_2 & q_0&p\\ p & p & p\\ \hline \end{array}$$

1. $q=q_0$.
1. $F=q_0$ is the final state. It corresponds to the intial state because the empty set is accepted by the automata.

Now, for a proof, the idea is the following. Let $A$ be a DFA that recognizes the language $L$. We are now going to construct an NFA $A'$ that recognizes the language $D(L)$. The alphabet, start, and accept states are the same as for $A$. However, for each transition in the original DFA $\delta(q,\alpha) = q'$, we add a new state $s_{q,q'}$ and make transitions $\delta(q,\alpha) = s_{q,q'}$ and $\delta(s_{q,q'},\alpha) = q'$. In this way, we ensure that whenever the automaton $A$ reads a symbol, $A'$ reads the same symbol twice.