Prove that if M is regular then sandwiched M is regular as well

Question

Hi I'm having some confusion with regular languages and DFAs.

Let's say we have some language M defined as $M = \{11, 1010\}$. Then let's define some $M[0]$ be defined formally as $\{x_10x_2...0x_n | x_i \in \Sigma, x_1...x_n \in M\}$ so $M[0] = \{101, 1000100\}$ Essentially strings in $M[0]$ are formed by taking a string from $M$ and inserting a $0$ between each character of the word.

We want to prove IN GENERAL that if $M$ is regular, so is $M[0]$.

I have already worked out that given M's regularity I can have a DFA representing it. Then I just need to work out a way to modify this DFA such that there is an additional state inserted between each of the states $q_0, q_1, \dots, q_n$ which appends an additional 0 to the string before it is accepted so that $$\{11, 1010\} \rightarrow \{101, 10000100\}$$

These additional states would bounce any 1 to a shared junk state which just loops back into itself for 0,1 to handle any binary strings we don't wish to accept. In this way we will accept the same strings as M and get our M[0] strings. Just wondering if this line of reasoning is right or if this is an unsound proof.

Answer 1

You're exactly right! The trick now is to say how to write this up formally.

So let's fix a DFA with a set of states $Q$, a transition function $\delta : Q \times \{0,1\} \to Q$, an initial state $q_0 \in Q$, and a set of accepting states $F \subseteq Q$. We want to build a new DFA that puts a new state between each of the old states that checks for a $0$, as well as a junk state to get sent to in case any of our new states see a $1$.

So let's define a new set of states $Q[0] = Q \cup \{ q_\text{new} \mid q \in Q \} \cup \{ \text{junk} \}$. Now anytime we used to have a transition $q \overset{a}{\to} q'$, we want to replace this with a transition $q \overset{a}{\to} q'_\text{new} \overset{0}{\to} q'$. That is, we intercept the arrow to $q'$ at the new state $q'_\text{new}$, and make sure our next input is a $0$ before continuing. Of course, we want to do this for every state $q \in Q$.

Do you see how to define our new transition function $\delta[0] : Q[0] \times \{ 0, 1 \} \to Q[0]$ which implements this behavior? I'll leave a hint under the fold.

When we're in a "new" state, we want to read a $0$, then go where we're supposed to go. So $\delta[0](q_\text{new}, 0) = q$ and $\delta[0](q_\text{new}, 1) = \text{junk}$. Of course, $\delta[0](\text{junk}, a) = \text{junk}$ is a sink. All that's left is to say what $\delta[0](q, a)$ should be for an "old" state $q$. Do you see how to finish this?

Then, with $Q[0]$ and $\delta[0]$ in hand, it's not hard to see that defining $q_0[0] = q_0$ and $F[0] = F \subseteq Q \subseteq Q[0]$ finishes your construction.

---

I hope this helps ^_^

Answer 2

Just to add to HallaSurvivor's answer, here is an alternative proof using the fact that regular languages are closed under homomorphisms and under left and right residuals.

Let $h:\{0,1\}^* \to \{0,1\}^*$ be the homomorphism defined by $h(0) = 00$ and $h(1) = 10$. Also recall that if $L$ is a language, then the right residual of $L$ by $0$ is the language $$ L0^{-1} = \{u \in \{0,1\}^* \mid u0 \in L\} $$ It remains to observe that $M[0] = h(M)0^{-1}$ to conclude.