Prove that a class of regular languages is closed under an operation 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?
 A: 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.

A: 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.
