Problem 1 Let 0 1 1 Here, Y2 contains all columns of 0s and 1s of height two. A string of symbols in Y2 gives two rows of 0s and 1s. Consider each row to be a binary number, where the first symbol is the least significant bit of each binary number. For example, the string 1 1 0 0 1 0 0 1 represents 0011 3 (top row) and 1001 9 (bottom row). Let C (w E the bottom row of w is 3 times the top row For example 1 1 0 0 1 0 0 E C, but 1 0 0 1 0 1 1 1. Let us first understand how one can compute the binary representation of 3 times another binary number. Consider the following example that multiplies 6 110 with 3 11 110 11 110 1100 10010 The first line above is the product of 1 with 110, and the second line is the product of 10 with 110 Thus, the first line is the same as the number we are multiplying 3 with, and the second line is just that number shift one position to the right. Finally, the last line is the sum of the first two lines; this requires keeping track of the carry. Now remember that we are seeing the bits from right to left (least significant bit first). To compute the bits of the product, we need the current bit of the first line (which is the current bit of the number we are seeing, the current bit of second line (which was the bit of the number we saw in the previous step), and the current carry. Thus, the DFA to solve this problem will remember in its state the carry from the previous position, and the previo bit seen (which is the bit in the second line We can formally, define the DFA M (Q, Y2, o, go, F) as follows