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

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?

• First try to describe an NFA that accepts the original language, except that the last 0 is changed into a special symbol X. So 0010011 would become 0010X11. – Hendrik Jan Feb 13 '18 at 0:20
• This can also be proved using closure operations. – Yuval Filmus Feb 13 '18 at 7:39
• Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – Raphael Feb 13 '18 at 10:37
• "I am trying to prove a transformed language" Trying to prove what about it? – David Richerby Feb 13 '18 at 15:39

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.
• (1) Using $\sigma$ is definitely not standard convention. In a formal language context, $\sigma$ is often a letter – an element of $\Sigma$ – but nothing beyond that. (2) It is indeed a standard result that regular languages are closed under inverse homomorphism. – Yuval Filmus Feb 17 '18 at 9:28