Closure of regular languages under deleting a 1 from each even run of 1s

Question

Let $R$ be a regular set over the alphabet $\{0, 1\}$. Give a machine construction to prove that the set obtained by deleting one 1 from each even length block of 1’s is also regular, and using closure properties for the class of regular sets.

Current Approach:

For the first part, using a machine construction, I was thinking that you take a simple FA that accepts only strings with an odd number of 1's (let's call this language $S$). This would be the simplest way of forcing strings in $R$ to have blocks of 1 of odd length. Then I would have some sort of $\epsilon/1$ transition to the original machines states where I would see if a string $x$ that is in the language $S$ would also be in $R$ if I were to add a 1 to any odd block of 1s.

I am unsure of how to describe that using the 5-tuple, $M = (Q, \{0,1\}, \delta, q_0, F)$, or if my methodology is correct. Any advice on where I should go and how I might prove closure in the two different ways is welcome.

Answer 1

Below you can find solutions for the similar problem in which we want to delete a single 1 from each odd length run of 1s. I'll let you adapt them to your question.

First, let me explain how to solve it using closure properties. We start with your language $R$. We then apply a regular substitution that optionally "marks" every 1, i.e. changes it into $\mathbf 1$. We intersect the resulting language with $0^*((11)^*(\mathbf{1}+\epsilon)0^+)^*((11)^*(\mathbf1+\epsilon)+\epsilon)$ – this has the effect of marking the final 1 out of each odd run. Finally, we apply a homomorphism that deletes all marked 1s.

Second, let me explain how to explicitly construct an NFA for the new language given an NFA for $R$. Let the NFA for $R$ be $\langle Q, \{0,1\}, \delta, q_0, F \rangle$. The new states will be $(Q \times \{0,1\}) \cup \{q_f\}$, and the new initial state will be $\langle q_0, 0 \rangle$; the second entry is the parity of the current run of 1s. The new accepting states are $(F \times \{0\}) \cup \{q_f\}$ (note that in the new language, all runs of 1s must have even length). It remains to define the new transition function:

• If there is a transition $q_1 \stackrel 0 \to q_2$, then we add a transition $\langle q_1, 0 \rangle \stackrel 0 \to \langle q_2, 0 \rangle$; that is, we allow the transition only if the parity of the current run of 1s is even.
• If there is a transition $q_1 \stackrel 1 \to q_2$, then we add the following transitions:
  1. $\langle q_1, 0 \rangle \stackrel 1 \to \langle q_2, 1 \rangle$ and $\langle q_1, 1 \rangle \stackrel 1 \to \langle q_2, 0 \rangle$; these just maintain the parity of the length of the run.
  2. If $q_2 \in F$: $\langle q_1, 0 \rangle \stackrel \epsilon \to q_f$. This handles odd runs of 1s at the very end of input.
• If there are transitions $q_1 \stackrel 1 \to q_2 \stackrel 0 \to q_3$, then we add the transition $\langle q_1, 0 \rangle \stackrel 0 \to \langle q_3, 0 \rangle$. This corresponds to deleting a 1 from the end of an odd run.