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?
Best Answer
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.