以下のサイトで勉強していると、「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)*であることがわかりました。
誤り、誤字、脱字などがあれば教えていただければ幸いです。