Describe construction of finite automata that accepts the language Double-Letter(L)

Question

Describe construction of finite automata that accepts the language Double-Letter(L), where Double-Letter(L) is in the language of words from L, except each letter in the word appears twice. So $abc\in L$ $\iff aabbcc \in $ Double-Letter($L$).

For example if L={a,aa,ab,ba} then Double-Letter(L) = {aa,aaaa,aabb,bbaa}

My idea: Create states Q that are named s and ss where $s\in \Sigma$. Make states named ss accepting if $ss \in L$

FA illustrated for the example above

What next? is this a good approach? I can't think of the next step on how to construct this doubled DFA for ALL languages.

Answer 1

The idea is to start with an automaton for $L$, and replace each transition labeled $\sigma$ by a path of length 2 both of whose edges are labeled $\sigma$. In order to make it a DFA, we also add a sink state. (This might be unnecessary in your definition of DFA.)

In more detail, suppose we start with a DFA $(Q,q_0,\delta,F)$ for $L$ (here $Q$ is the set of states, $q_0$ is the initial state, $\delta$ is the transition function, and $F$ is the accepting states). We construct a DFA whose set of states is $Q \cup Q \times \Sigma \cup \{q_{\mathit{sink}}\}$, where $\Sigma$ is the alphabet. The initial state is still $q_0$, and the accepting states are still $F$. The transition function $\delta'$ is defined as follows:

• $\delta'(q,\sigma) = (q,\sigma)$ (this is a member of $Q \times \Sigma$).
• $\delta'((q,\sigma),\sigma) = \delta(q,\sigma)$.
• $\delta'((q,\sigma),\tau) = q_{\mathit{sink}}$ if $\tau \neq \sigma$.
• $\delta'(q_{\mathit{sink}},\sigma) = q_{\mathit{sink}}$ for all $\sigma \in \Sigma$.

A simpler way of proving that the regular languages are closed under Double-Letter is using regular expressions: given a regular expression for $L$, simply double each letter. This is a special case of closure under homomorphism and regular substitution.

Answer 2

This a hand drawn solution to your problem, I'll explain the transitions,

Before you see the diagram, note that those are not 2 different DFAs, but I have drawn one more transition of states q1, q3, q5 to make the image more clear, as it is already very messed up.

q0 is the start state, machine has not seen anything until now.

On scanning the first symbol, suppose, it turns out to be 'a'

d(q0, a) -> q1 (d is the transition function)

machine is in q1 now.

If it sees another 'a' it will reach q2 which CAN BE the final state,

else it will reach q7 from where it will never reach any final state because 'a' has not repeated.

from q2, if machine see another 'a' it will go back to q1 else it will go to q3 on seeing a 'b' or q5 on seeing a 'c'

Same thing goes on for 'b' and 'c'

After scanning the complete string, if the machine is in final state then the string is in the language else, it is not in the language.

This assumes that the empty string epsilon is not in Double-Letter(L)

In that case q0 will be also be a final state.