I don't know if this question should have better been on math.Stackexchange
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 tha language $Double(L)$.
I shouldn't use equivalence between automatas and regular expressions
goal : I therefore deduce that I have to prove that autmomatas are closed by the Double operation.
the hypothese : is that it exists a language $L$ such taht it exists an automata $A$ which recognizes it.
proof attempt : $D(L)$ being a language, it must be a automata associated.
But:
- has(have ?) every language(s?) an associated automata?
- Isn't this proof too short or taking its goal has an hypothesis ?
Proof attempt n°2
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.
- $Q=\{q_0, q_1, q_2, p\}$, $q_1,q_2$ are waiting states, $p$ is a bin state.
- $\Sigma$ is the alphabet. For the example it is : $\{a,b\}$.
- $\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}$$
- $q=q_0$.
- $F=q_0$ is the final state. It corresponds to the intial state because the empty set is accepted by the automata.