1. Present a Mealy Machine that computes the decrement function on binary numerals. That is, given a binary numeral representing a positive integer k, it outputs the binary numeral representing k-1. The bits of both the input and output strings are to go from least to most significant, which is the reverse of the standard form.
As an example, an input of 001011 should result in an output of 110011, corresponding to (in terms of decimal numerals) 52 - 1 = 51.
2. Present a Mealy Machine that computes the subtraction function on binary numerals. That is, given a pair of binary numerals representing k and m, respectively, where it is assumed that k ≥ m, it outputs the binary numeral (with leading zeros allowed) representing k − m.
The input alphabet is {0,1} × {0,1}, in other words { [0,0], [0,1], [1,0], [1,1] }. For example, an input of [0,1][0,1][1,0][1,1][0,0][1,0] represents the problem instance 001101 - 110100, in which (as in Problem 1) the bits of the numerals go from least to most significant. Here, the output should be 100001. This corresponds to (in terms of decimal numerals) 44 - 11 = 33.Here is a second example: The input [1,0][0,1][1,1][1,0][0,0][1,0] should produce 111001, corresponding to 45 - 6 = 39.
3. Present a Mealy machine that, given a bit string x = x0x1x2...xn as input, produces as output the bit string y = y1y2y3...yn, where, for each i,
| yi = { | 0 | if xi-1 = xi |
| 1 | if xi-1 ≠ xi |
Thus, each occurrence of 1 in y indicates an occurrence of either 01 or 10 in x, whereas each occurrence of 0 in y indicates an occurrence of either 00 or 11 in x. For example, if x = 00011101100, then y = 0010011010
4. Present a Mealy machine that, given as input a bit string, echoes that bit string, except that it truncates any run of length greater than two.
A run within a string is a substring all of whose symbols are the same and such that any symbol appearing to its immediate left or right is different. For example, if u and v are strings over the alphabet {0,1}, then in u0000v, the indicated occurrence of 0000 is a run iff u ends with 1 (or is empty) and v begins with 1 (or is empty).
Thus, the machine you are to describe would produce 0102120110120 (i.e., 0100110110110) as output in response to the input 0105130110160 (i.e., 010000011101101111110). (Each run of bits of length greater than two in the input string appears as a run of length two in the output string.)