以下のサイトで勉強していると、「3で割りきれる2進数の正規表現」というテーマが出てきました。

結論から言うと、(1+1(01*0)*1)*です。
(「+」を「または」の意味で使っています。)

なぜそうなるのかが記載されていなかったので、導出しました。

（以下導出）

nを非負整数として、2^nを3で割った余りは、以下の様になります。

2^0 → 1
2^1 → 2
2^2 → 1
2^3 → 2
2^4 → 1
...

このことから、2^(2n) mod 3 = 1, 2^(2n+1) mod 3 = 2 (nは非負整数) がわかります。

ここで、2進数において、偶数桁にある1の数をeven1、奇数桁にある1の数をodd1とします。

先ほどの考察から、3で割り切れる2進数は、

(2(odd1) + (even1)) mod 3 = 0
⇔ ((even1) - (odd1)) mod 3 = 0

が成り立っていることがわかります。

つまり正規言語は、
{w | wを2進数とみなすと ((even1) - (odd1)) mod 3 = 0}
となります。

しばらく手を動かしてみると、これを受理するような有限オートマトンは、以下の様になるとわかります。ただし、受理状態はAです。
（マウスで描いたので気持ち悪いかもしれません。）

最終的に状態Aに遷移するような言語の正規表現を導出します。
ただし、以下の記事にあるArden's theoremを前提知識とします。

上記のオートマトンによる言語方程式は、以下の様になります。

A = ε + A0 + B1 (1)
B = A1 + C0 (2)
C = B0 + C1 (3)

(3)より、C = B01* (3)' (∵Arden's theorem)
(2)と(3)'より、B = A1(01* 0)* (2)' (∵Arden's theorem)
(1)と(2)'より、A = (0+1(01*0)*1) * (∵Arden's theorem)

求める正規表現は、受理状態であるAの、(0+1(01*0)*1)*であることがわかりました。

誤り、誤字、脱字などがあれば教えていただければ幸いです。