Prove that a class of regular languages is closed under an operation

Question

We define an operation addone on any string in $\Sigma^*$ that adds a $1$ after the leftmost bit if such a bit exists. For example, $\operatorname{addone}(010)$ is $0110$, $\operatorname{addone}(00)$ is $010$, and $\operatorname{addone}(\epsilon)$ is still $\epsilon$. Now for any language $L \subseteq \Sigma^*$, extend the operation as

$\operatorname{ADDONE}(L) = \{ \operatorname{addone}(w) \mid w \in L\}$.

That is, the new language $\operatorname{ADDONE}(L)$ is obtained by applying the operation $\operatorname{addone}$ to all strings in $L$. Show that the class of regular languages is closed under the operation $\operatorname{ADDONE}$ (Describe your construction informally and prove that it works).

Sorry about the lack of formatting. I'm wondering if I need to use induction to prove something like this?

Answer 1

Setting \begin{align} L_0 &= 0^{-1}L = \{u \in \{0,1\}^* \mid 0u \in L\} \\ L_1 &= 1^{-1}L = \{u \in \{0,1\}^* \mid 1u \in L\} \\ L_\epsilon &= \begin{cases} \{\epsilon\} & \text{if $\epsilon \in L$} \\ \emptyset & \text{otherwise} \end{cases} \end{align} one has $\operatorname{ADDONE}(L) = L_\epsilon \cup 01L_0 \cup 11L_1$. Now the languages $L_0$ and $L_1$ are Brzozowski derivatives of the regular language $L$ and thus are also regular. Finally, $\operatorname{ADDONE}(L)$ is obtained from regular languages using union and product and hence is also regular.

Answer 2

If we define regular languages as follows, we can prove the assertion by induction as you said.

A regex is one the following:

• $\emptyset$
• $\varepsilon$
• $0$ or $1$
• append of two regex denoted by $r_1r_2$
• union of two regex denoted by $r_1+r_2$
• star of regex denoted by $r^*$

Now we can prove by induction.

• $\text{ADDONE}(\emptyset) = \emptyset$ is still regex
• $\text{ADDONE}(\varepsilon) = \varepsilon$ is still regex
• $\text{ADDONE}(0) = 01$ and $\text{ADDONE}(1) = 11$ are still regex
• This is the hardest case. There are two possibilities.
  • If $r_1$ doesn't contain $\varepsilon$ then $\text{ADDONE}(r_1r_2) = \text{ADDONE}(r_1)(r_2)$ and $\text{ADDONE}(r_1)$ is regex by induction hypothesis so the whole term is regex.
  • If $r_1$ contains $\varepsilon$ then we can remove it from the $r_1$ and achieve $r_1'$ (this is easy to prove that regex is closed under subtraction), so we have $r_1 = r_1' + \varepsilon$ and

$\text{ADDONE}(r_1r_2)$

$ = \text{ADDONE}((r_1' + \varepsilon)r_2)$

$ = \text{ADDONE}(r_1'r_2 + \varepsilon r_2)$

$ = \text{ADDONE}(r_1')(r_2) + \text{ADDONE}(r_2)$ (left part is regex as described in the other case, and second part is regex by the induction hypothesis, so the whole term is regex.)

• $\text{ADDONE}(r_1+r_2) = \text{ADDONE}(r_1) + \text{ADDONE}(r_2)$ is still regex
• We know that $r^* = rr^*$ so this is just like the $r_1r_2$ case.