CS 334 Automata and Computation

Problem 4. (10 points) Let Dk denote the set of binary strings that represent numbers divisible by k. For example, input strings 0,00,000, 10,010,0010,0100010 are all divisible by 2 (the least significant bit is the rightmost, or last symbol in the sequence), and therefore are all in the language D2. 1. Construct a deterministic FSA to recognize the language D3. Hint: As you process the input use a state to maintain the value of the remainder of the input processed thus far. 2. Prove that Dk is regular, for every k 2 1