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.

  • $\begingroup$ Another way to look at it: L' is the language of all strings with no even length runs of 1's, which would be accepted by L if a 1 was added to none, some or all odd length runs of 1's. I think you should be able to generate a FSM for that. $\endgroup$
    – gnasher729
    Commented Oct 22, 2020 at 9:29

1 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.
  • $\begingroup$ For the claim that if $q_2 \in F$, the new transition is $(q_1, 0) \rightarrow q_f$ on $\epsilon$, why is this? Wouldn't it be $(q_2, 0) \rightarrow q_f$ on $\epsilon$? $\endgroup$ Commented Sep 23, 2018 at 23:06
  • $\begingroup$ The idea is that $q_f$ plays the role of $q_2$ here. $\endgroup$ Commented Sep 24, 2018 at 1:06
  • $\begingroup$ Oh I see, thanks for your clarification! $\endgroup$ Commented Sep 24, 2018 at 1:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.