4
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Hendrik Jan Feb 13 '18 at 0:20
  • $\begingroup$ This can also be proved using closure operations. $\endgroup$ – Yuval Filmus Feb 13 '18 at 7:39
  • $\begingroup$ 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! $\endgroup$ – Raphael Feb 13 '18 at 10:37
  • 2
    $\begingroup$ "I am trying to prove a transformed language" Trying to prove what about it? $\endgroup$ – David Richerby Feb 13 '18 at 15:39
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It would have helped me to state explicitly that “σ” stands for a binary digit — is that a standard convention in computer science? It is presumably a standard result that applying the inverse of a many-to-one letter-wise function to a regular language produces a regular language — at least it seems obvious enough in terms of automata or REs. At any rate you have done the job, though I still need to think how to apply this to automata. $\endgroup$ – PJTraill Feb 16 '18 at 21:22
  • $\begingroup$ (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. $\endgroup$ – Yuval Filmus Feb 17 '18 at 9:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.