How to prove that a transformed language is regular using an NFA

Question

I am trying to prove that if a language $ L $ of binary strings (i.e. a subset of [01]*) is regular then so is the transformed language $ plus (L) $ consisting of the binary representations of those integers one greater than those represented by the elements of $ L $. That is to say $ plus (L) = \{ plust (l) : l ∈ L \} $ where $ plust $ transforms a binary of an integer $ n $ to a binary of $ n + 1 $, so $ plust ("0111") = "1000" $.

I am trying to prove this by assuming that there is a DFA that accepts $ L $ and using it to build an NFA that accepts $ plus (L) $.

However, I am totally at a loss as to how to do this. What is a good starting point, or what steps can I take to produce such a proof?

Answer 1

Here's how to do it using closure operations; a similar idea can be used for constructing an NFA.

There are three cases to consider. The first case is words consisting only of ones. In this case, we want to transform $1^n$ to $10^n$. We accomplish this as follows. Let $h\colon \{0,1\} \to \{0,1\}^*$ be the homomorphism defined by $h(0) = 1$ and $h(1) = 0$. We capture this part of $\operatorname{plus}(L)$ by the expression $1h(L \cap 1^*)$.

The second case is words of the form $1x01^n$, which should be transformed to $1x10^n$. Here the construction is a bit more complicated. Let $a\colon \{0,1,0',1'\} \to \{0,1\}^*$ be defined by $a(\sigma) = a(\sigma') = \sigma$ (where $\sigma \in \{0,1\}$). The expression $a^{-1}(L) \cap 1(0+1)^*0'1'^*$ replaces $x01^n$ with $x0'1'^n$. To complete the transformation, define $b\colon \{0,1,0',1'\} \to \{0,1\}^*$ by $b(\sigma) = \sigma$, $b(0') = 1$, and $b(1') = 0'$. The expression $b(a^{-1}(L) \cap 1(0+1)^*0'1'^*)$ handles this part of $\operatorname{plus}(L)$.

The final case is the word $0$ (if it is in $L$), which should be transformed to $1$. This is accomplished by $h(L \cap 0)$.

In total, we obtain $$ \mathrm{plus}(L) = 1h(L \cap 1^*) \cup b(a^{-1}(L) \cap 1(0+1)^*0'1'^*) \cup h(L \cap 0). $$ Note that any words in $L$ which are not binary encodings (in other words, the empty string and strings with leading zeroes) are just ignored. This can of course be changed if wanted.