2. Binary addition. This problem is about two ways of representating addition of binary natural numbers. We consider 0 to be a natural number, we allow binary representations of natural numbers to have leading 0 s, and we consider to be a binary representation of 0 . When adding numbers, we do not allow overflow, so, for example, 1111+0001=0000 is false. (a) [Problem 1.32] Let 3=000,001,010,011,100,101,110,111, that is, an alphabet of eight symbols, each of which is a 3-tuple of binary digits. Thus, a string over 3 gives three rows of binary digits. Show that the following is regular: B={w3 the bottom row of w is the sum of the top two rows }. Hint: Since it's easier to think about addition from right to left, design an automaton for BR first, then convert it into an automaton for B. (b) [Problem 1.53] Let ={0,1,+,=}, and prove that the following is not regular: ADD={x=y+zx,y,z{0,1}andx=y+zistrue}