10. The two's complement of a binary string, representing a positive integer, is
formed by first complementing each bit, then adding one to the lowest-order
bit. Design a transducer for translating bit strings into their two's
complement, assuming that the binary number is represented as in Example
1.17, with lower-order bits at the left of the string.
11. Design a transducer to convert a binary string into octal. For example, the bit
string 001101110 should produce the output 156.
12. Let a 1 a 2 …be an input bit string. Design a transducer that computes the
parity of every substring of three bits. Specifically, the transducer should
produce output
For example, the input 110111 should produce 000001.
13. Design a transducer that accepts bit strings a 1 a 2 a 3 …and computes the
binary value of each set of three consecutive bits modulo five. More
specifically, the transducer should produce m 1 , m 2 , m 3 ,…, where
14. Digital computers normally represent all information by bit strings, using
some type of encoding. For example, character information can be encoded
using the well-known ASCII system.
For this exercise, consider the two alphabets {a, b, c, d} and {0, 1},
respectively, and an encoding from the first to the second, defined by a →
00, b → 01, c → 10, d → 11. Construct a transducer for decoding strings on
{0, 1} into the original message. For example, the input 010011 should
generate as output bad.
15. Let x and y be two positive binary numbers. Design a transducer whose
output is max (x, y).