A simpler solution is to use modular arithmetic (this works for any base). If we consume a binary number from left to right, let N be the binary value already

A simpler solution is to use modular arithmetic (this works for any base). If we consume a binary number from left to right, let N be the binary value already expressed. If we then consume a 0, then the new value is now 2N. If we consume a 1, then the new value is 2N+1. Create a 3-state machine where state 0 represents a running value of N mod 3. Starting state is 0. Follow all the transitions. e.g. from state 2 (N = 2 mod 3), if we consume a 0, we are now at 2N + 1 = 1 mod 3, so f(2,0) = 1. Full transition function is: f(0,0) = 0, f(0,1) = 1 f(1,0) = 2, f(1,1) = 0 f(2,0) = 1, f(2,1) = 2 This is trivial to turn into the regex (0|1(01* 0)* 1)* (had to add spaces to stop italicisation). If leading zeroes are a problem you have to modify the FSM a little which makes the resulting regex a little more complicated.