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

Question

I am trying to prove a transformed language plus(L), which transforms a binary of an integer to a binary of n+1. So plus(0111) would be 1000

I am trying to prove this by using the assumption that there is an arbitrary DFA that accepts the original language and by building an NFA that accepts this new language.

However, I am totally lost of how to do this. What is a good starting point, or what are the steps that I have to use to solve this kind of proof?

Answer 1

I would start with thinking about what strings are in this language from the smallest going up "1","10","11", "100", "101". Then thinking if their are any patterns.

Well it looks like the first pattern "starts with one". So from my start state I would have an arc tagged with "1" to a second state. Since "1" is a valid string in this language the second state is also a final state.

Then I would examine the strings after the first one has been consumed "0", "1", "00", "01", ... and I would see that by adding arcs from the second state back to itself that would match all of those states.

Answer 2

Construct a DFA that subtracts one from the input string. Then feed the output to the DFA that accepts $L$.

The following DFA starts with initial state $s_0=-1$ and subtracts $1$ from the input sequence $u_k$.

That is, given a string $u=u_n u_{n-1} \cdots u_0 \in \{0,1\}^*$, with output $y=y_n y_{n-1} \cdots y_0$, then $v(y)=v(u)-1$ where $v$ is the binary value of the string parameter, and $y$ is computed as $y_k = \text{out}(s_k, u_k)$, $s_{k+1} = \text{next}(s_k, u_k)$ using the following table:

\begin{array}{|c|cc|} \hline s& \text{next}(s,u) & \text{out}(s,u)\\ \hline -1& \bar{u}& \bar{u}\\ \hline 0& 0& u\\ \hline 1& \bar{u}& \bar{u}\\ \hline \end{array}