Sipser 2.33

Let Σ2 = {[0; 0], [0; 1], [1; 0], [1; 1]}
C = { w ∈ Σ2* | the bottom row of w is 3 times the top row }

If you multiply a number by 3, you add the number to itself left-shifted by 1 bit. For example

  1011

  * 11

  ----

  1011

 10110

 -----

100001

Using the above idea, we can make a machine for the reverse of the language. There are now 2 things to remember: the previous symbol and any carry from the previous column. There are 4 states:
          previous symbol   carry
s00        0                           0
s01        0                           1
s10        1                           0
s11        1                           1

Sipser 2.32

Let Σ3 = {[0; 0; 0], ... [1; 1; 1]}
B = { w ∈ Σ3* | the bottom row is the sum of the top two rows}

Since addition is carried out from right to left, we can make a machine for the reverse of this language. If we add 2 bits in one column with a possible carry from a previous column, the sum can be at most 1+1+1 = 11.  Therefore the carry can either be 0 or 1 and that is what we have to remember at any stage. Therefore there can be 2 states: 'carry 0' and 'carry 1' (here you add a carry of 1 to the top 2 bits).

For example if you are in the 'carry 1' state and you see a [0; 0; 0] you go to the dead state (because 0+0+1 = 1 and the bottom bit is a 0). But if you see a [0; 1; 0], 0+1+1 = 10 and you loop back to the 'carry 1' state. Since there shouldn't be any carry out of the left-most column, 'carry 0' is the accept state.

Sipser 2.56

If A is a set of natural numbers and k is a natural number greater than 1, let
Bk(A) = {w | w is the representation in base k of some number in A}
For example, B2({3,7}) = {11, 111} and B3({3,7}) = {10, 21}

So the question asks us to give an example of a set A for which B2(A) is regular and B3(A) is not.

Well one thing is obvious, the set must be infinite. Otherwise you can always make a finite state machine for it. That observation doesn't help much :)

Try 1: A = set of all even numbers
Base 2 - The regular expression Σ*0 covers it.
Base 3 - It wasn't immediately apparent to me how to do it in base 3. But it can be...

We can have 2 states, one for remainder 0 and the other for remainder 1. 'remainder 0' is the accept state. Suppose the next input symbol is 2.  If the input string so far represents x and we stick a 2 on the end, the new number will be 3x+2. If the old remainder was r, the new remainder will be (3r+2) mod 2. We can manage the transitions for other input symbols in a similar way.

Try 2: A = set of all powers of 2
Base 2 - 10*
Base 3
Here I am stuck. I cannot figure out a machine that will recognize this set.
If I want to show that this set is not regular, I guess I'll have to use the pumping lemma. But given an arbitrary number p, I can't think of a string longer than p symbols that is guaranteed to be a power of 2.
There's a big dilemma about the pumping lemma...Any help?

Sipser 2.43: DROPOUT(A)

Let A be any language. DROPOUT(A) is defined as the language containing all strings that can be obtained by dropping one symbol from a string in A. We have to show that the class of regular languages is closed under the DROPOUT operation.
DROPOUT(A) = {xz | xyz ∈ A, where x,z ∈ Σ*, y ∈ Σ}

This means that given a DFA for A, we have to construct a DFA/NFA for DROPOUT(A).  This looks like a good opportunity to introduce ε-transitions. Let [A]1[B] represent a transition from state A to state B on a 1. If we replace this with [A]ε[B], then if we ever reach state A, we go directly to state B without reading any input. In effect we will have dropped the 1.

But the symbol to drop can occur at any position in the string. So I thought I will make a copy of the given DFA for each state it contains. In that copy, I will put ε on all arrows going out of that state. Then a union of all these copies would be the required NFA. However I think there is a problem with this idea. If the state occurs in a loop, then it would be possible to drop 2 or more symbols and still end up at the accept state.