Multiplying by three is the same as shift + add. Essentially you have a binary adder with carry, or rather two carries: the input bit is also a carry. So you have an FSM with three states for the three possible carry values 0, 1, 2.
00111
+ 00111
--------
10101
Let's start with a recursive regex with groups for each of the states.
qr/ (?(DEFINE)
( 00 (?1) | 11 (?2) | ) # group 1: carry = 0
( 01 (?1) | 10 (?3) ) # group 2: carry = 1
( 00 (?2) | 11 (?3) ) # group 3: carry = 2
)
\A(?1)\Z /x;
From here, we can inline the group 2 in g1 and g3:
qr/ (?(DEFINE)
( 00 (?1) | 11 01 (?1) | 11 10 (?3) | )
( )
( 00 01 (?1) | 00 10 (?3) | 11 (?3) )
)
\A(?1)\Z /x;
Now it should be obvious that the group 3 i.e. carry=2 state is entered with a
11 10 and left with
00 01. Rewriting the regex with repeats instead of recursion:
my $Regex_Pattern =
qr/ \A ( 00 | 11 01 | 11 10 ( 00 10 | 11 )* 00 01 )* \Z /x;
ps. I'm assuming that the input string must have 2*n digits.