| You can construct a regular expression / state machine for these fairly easily. Let X be the number we have seen so far. State A: X mod 3 = 0
State B: X mod 3 = 1
State C: X mod 3 = 2 We'll need a separate start state if you swing that way. Now, observe what happens if we have interpreted a binary number and then suddenly stick a 0 at the end of it. It gets multiplied by 2. Not shocking. If we stick a 1 at the end of it, it gets multiplied by 2 and one gets added. Still not that hard. OK, I'm going to rename our states now. Instead of X, we're going to describe them in terms of k. k is some positive integer which is a multiple of 3 -- we don't care which. A: k + 0
B: k + 1
C: k + 2 Now, if we multiple k by 2, we get 2k, which we know is also going to be divisible by 3 because k is. So a 0 transitions A to A. If we multiply k by 2 and add 1, we get 2k + 1. 2k + 1 % 3 = 1, because 2k is evenly divisible by 3. So a 1 transitions A to B. The next four transitions are left as an exercise for the reader -- they're pretty trivial. You can use this same general pattern to construct any "divides by N" state machine. Going from a state machine to a regular expression (particularly the smallest possible regular expression) is a bit trickier. |