3の倍数にマッチする正規表現
([0369]|[147]([0369]|[147][0369]*[258])*([258]|[147][0369]*[147])|[258]([0369]|[258][0369]*[147])*([147]|[258][0369]*[258]))+
なんかさっそく横長ですいませぬ。
多分これであってるはず。3の倍数にマッチする正規表現です。
最短解であるかどうか保証は無いけどとりあえず過不足なくマッチするっぽい。
で、ちょいと冗長すぎて読みにくいんで、[0,3,6,9]を0と言ったように省略して、適当に改行/スペースをいれるとこんな感じ。
( 0 | 1 (0 | 10*2)* (2 | 10*1) | 2 (0 | 20*1)* (1 | 20*2) )+
なんとなく分かるかと思います。
なんとなく分からない方のために3の倍数に関するいくつかの性質。
なんか偉そうですいません。
10進数の場合、3の倍数は、というか3で割った余りは「各桁の数の和」と同じになる、という性質を持ってます。
例えば、145251367という数があった場合、3で割った余りを求めるには、各桁をすべて足して、
1+4+5+2+5+1+3+6+7=34
とやって、3で割った余りを求めりゃいいのです。この場合1ですね。
ここで出てきた34も同様に、3+4=7とやってもやはり1が余りとなります。
数学的にちょこっ補足すると、
例えば、12345という数は
1*10000 + 2*1000 + 3*100 + 4*10 + 5
という風に分解できて、これはさらに、
1*9999 + 2*999 + 3*99 + 4*9 + 1 + 2 + 3 + 4 + 5
のように変形できる。
で、この前半部分の9...を含む部分は全部3の倍数なので、3で割った余りだけを考えるなら無視できるので
12345 ≡ 1+2+3+4+5 (mod. 3)
となると。
ちなみに、前半部分は9の倍数でもあるので、9でも同じことができます。
あと、16進数の場合は0xF = 15 = 3 * 5なので、3,5,15で割った余りを簡単に出すことができます。
覚えておくと意外に便利...かも。
0x12345 ≡ 0x1 + 0x2 + 0x3 + 0x4 + 0x5 (mod. 3/5/15)
で状態遷移図の話に入ります。
この3で割った余り(以下めんどいので単に「剰余」と書きます)をもとめる状態遷移図を作ってみる。
さきほどの話を状態遷移図を書きやすいように再帰的に書き下して見ると、
長さ(桁)がゼロの数、つまり0は剰余は0になる。
で、ある任意の数nがあったときに、その後ろに一桁の数をくっつけた数、つまりm=n*10 + x (0≦x≦9)の剰余は、
nの剰余と、xの剰余の和、その剰余に等しい
ということになる。
...なんか余計わかりづらいような...ということで具体例挙げると、
1234は1+2+3+4=10なので、剰余は1ということがわかる。
で、ここに5をを付け加えると12345になるが、この剰余は1234の剰余1と、5の剰余2を足した数、つまり3、この剰余に等しい、ということなので、12345の剰余は0になるのです。
じっさい1+2+3+4+5=15,1+5=6で剰余が3であることが分かります。
まぁ、あたりまえ、といえば当たり前なのデスが。
で、状態遷移図がこちら
クソ汚い図ですいません。久々にペンタブ触ったのですが...
とちゅうで開き直りました。
で、まぁ、状態遷移図なんですが、丸の中の数字が「今の剰余」になります。(以下、(0)の様に丸括弧で表現します)
で、矢印のそばにかかれている数字が付け加わるとその矢印にそって遷移していきます。
ちなみに、スタート位置、つまり、初期状態は虚無から矢印が伸びてる(0)になります。
例えば一番最初に挙げた例の145251367を状態遷移させてみると、
1で(0)→(1)に遷移
4で(1)→(2)に遷移
5で(2)→(1)に遷移
2で(1)→(0)に遷移
略
6で(0)→(0)に遷移
7で(0)→(1)に遷移
のように、足し算せずに剰余を求められるのです。
この状態遷移図を元に正規表現を作ってみたいと思います。
性質→状態遷移図→正規表現
で、ここまで引っ張っておいてあれなのですが、じつは状態遷移図から正規表現を書く正しい方法、というか一般則を知らなかったりします(ぇ？
いや、多分うまくいくのではないかな、とか思うのですが自信無いです。
というか、上の正規表現書いてた時はほとんど直感で書いていたので(苦笑
直感はあかんだろ、といろいろ状態遷移図こねくりまわしたりして、どうにかこうにか発見した(?)方法でする。
今回のケースは初期状態と最終状態が同じ、かつ各状態から他の状態へ直接遷移可能という結構アレなケースですので、一般的に使えるかどうか...(д)
という、なんとも不安やっぷりなオレオレ正規表現ジェネレータの説明です。
まず、この状態遷移図から、状態である(0)から、出ているすべての矢印、及び、その行き先、つまり、直接遷移できる状態を列挙します。
- [0369]で(0)
- [147]で(1)
- [258]で(2)
で、これらの矢印を消してしまいます。
というのも、(0)は初期状態かつ最終状態なので、(0)に戻ってしまったらそこで終了して、全体を"+"なり"*"などの繰り返しで括ってやればいいのです。
って、あっー。
最終状態描き忘れたorz
えっと、3の倍数にマッチする正規表現、なんで、(0)が最終状態でする。
で、以下は、この遷移図を元に、列挙した各状態から最終状態(0)を目指します。
そして、最終的に(0)にたどり着けたルートをすべて"|"(選択)でつなぎます。
まず、(0)の場合ですが、これはなにもできません、というのも、矢印が全部消えてしまったので...。
とはいえ、(0)は最終状態でもあるので、これはひとつの答えでもあります。
ということで今のところの正規表現
[0369]+
すくなっ!!
つぎに(1)の場合、というか、(2)も対称形なので(2)の場合は説明省きます。
(1)から(0)へ向かうルートは単純に考えて、(0)へ直帰する方法と、(2)を経由して(0)へ向かう方法の二種類が考えられます。
このどちらも許容したいので"|"を使います。
( [0369] | [147] ( [258] | /* (2)→(0) */ ) )+
で、このままだと自分へ戻る矢印を処理できでません。
そこで、(1)→*(1)へと遷移するすべて探します。(*付きは直接遷移だけでなく、複数回遷移した末にたどり着くのも含める、という意味です。)
のですが、意外にこれがやっかい。ループしてたりなんやりと...。
で、よくよく考えてみると(1)→*(1)という遷移というのは、初期状態、最終状態がともに(1)である遷移図である、とも言えます。つまり、(0)にやったような処理を再帰的に施していけばいいのです。多分。
ということで、(1)からの直接遷移の範囲をしらべて、矢印を消していきます。
- [258]で(0)
- [0369]で(1)
- [147]で(2)
で、(0)から(1)にいく手段はないので却下。
(1)は矢印がないけど、最終状態なんでよし。
(2)からはというと、ほんとはまた再起しないといけないんだろうけど、ここまで単純になったらそのまま直感でえぇよね？[0369]*[258]で(1)に戻れます。
これらをやっぱり"|"でつないで、"*"で括ればok。
自分自身への遷移なのでやってもやらなくても、あるいは何回やっても同じなので。
ということで、今のところの遷移図
( [0369] | [147] ( [0369] | [147][0369]*[258] )* ( [258] | [147]/* (2)→(0) */ ) )+
だいぶそれっぽくなってきた。
で、さっき、軽々しく(2)を経由してー、とか言っちゃったのだが、よくよく考えればこれも(0)→(1)の時のようにいろいろやってやらないといかんわけだ。
これまた、(1)からの直接遷移を...って、あ、さっきと同じ図だ。
で、ここから(2)→(0)を探すわけだが...。
例のごとく手抜きして[0369]*[147]でok。
( [0369] | [147] ( [0369] | [147][0369]*[258] )* ( [258] | [147][0369]*[147] ) )+
あとは、(2)も同様にして、
( [0369] | [147] ( [0369] | [147][0369]*[258] )* ( [258] | [147][0369]*[147] ) | [258] ( [0369] | [258][0369]*[147] )* ( [147] | [258][0369]*[258] ) )+
完成♪
...全然わかんねぇ。
自分で書いておいてなんだが、あれだ、余りにひどすぎる。
ちぅことで、memoタグ入れておこうw
