Sipser Exercise 1.33


Take .

Write the function to denote the value of a string when taken as a binary number with most significant digit first.

If let

Then consider the language , that is, the binary value of the concatenation of the right-hand numbers is three times that of the left hand numbers.

We build a DFA that accepts , that is, strings satisfying the same numerical properties as above, but starting with the least significant digit.

First, suppose , i.e., a binary string with MSB first. Then,

So is added with a shifted copy of itself. So, a naive way to express the condition that is:

Which is almost correct, but we need to account for carry.

Let be an input to our DFA. Our machine will emulate a full adder. That is, upon reading , it will check that (mod 2), accounting for carry bit, and remember if a carry bit was introduced or used up in that addition. This means we need to remember value of and whether or not there is currently a carry bit, which will require four states. If ever , the machine goes into a dead state.

Obviously, states with carry bits cannot be accepting, because the presence of a carry bit means that the addition is not ‘complete’ without writing down another 1. In addition, if , the current value of would certainly require one more digit, so this state cannot be accepting either. The only accepting state is with no carry bit.

So let . The number denotes the value of and superscript denotes the presence of a carry bit. is the dead state. Then the following is a DFA that accepts

Then is regular and is also regular (by 1.31).