↑この記事について、「2進数だったら現実的なサイズの正規表現で書けそう」と思ったので書いてみます
おさらい: 7の倍数かを判定するオートマトン
7の倍数であるというのは、言い換えると 7で割ったときにあまりが0である ということです。これをもとに、ある数字を7で割ったときの余りを状態に持つオートマトンを考えます。このオートマトンは状態が0のときに受理状態になります(=7の倍数)。
このオートマトンの遷移には筆算の考え方が使えます。筆算ではまず一番上の桁をみて7で割り、そのあまりを10倍して次の桁での計算に利用していく、という流れです。それをもとにオートマトンを書いてみるとこんな感じになります。
- 12345 を 7で割ってみる
- オートマトンの状態に1 mod 7を格納 (状態: 1)
- 状態を10倍して、次の桁を足す (状態: 1*10 + 2 = 12)
- 7で割る (状態: 12 mod 7 = 5)
- 状態を10倍して次の桁を足す (状態: 5*10 + 3 = 53)
- 7で割る (状態: 53 mod 7 = 4)
- これを最後の桁まで繰り返す
最後までいくと状態は4になります。これは受理状態じゃないので、7の倍数でないとわかります。
これで、筆算的な考え方で与えられた数字を7で割ったあまりを計算するオートマトン ができました。なんとなく概要は掴めたと思います。
2進数で7の倍数を表す正規表現
元記事では10進法で考えていましたが、状態遷移パターンが多くてかなり長い正規表現になっていました。この記事では2進法で考えます。
まずは7で割ったときの余りを計算するオートマトンを考えます。このオートマトンの遷移は次のとおりです。
図の各マスは状態を表しており、辺が遷移を表します。たとえば今の状態が1で1が入力されたら3へ遷移します(2進数で 11 = 3、3 mod 7 = 3)。
状態数を減らしていく
ここから非受理の状態を減らしていき、正規表現へ持ち込みます。まず、状態6に止まるべきだった入力はそもそも受け付けない(非受理とする)として、状態6を削除します。すると、3 -> 6 -> 5
という遷移が3 -> 5
にまとめられます。
このように非受理のもの状態数を減らしていきます。ただ、この作業、恐ろしく面倒くさくて大変なので、状態が2つになった場面まで飛ばします。
辺に書かれている正規表現が大変なことになっていますね。
最後に状態2も削除します。これで0のときだけ受理するオートマトン、つまり7の倍数を判定するオートマトンが完成しました。あとは正規表現に落とし込んで完了です。
2進数で7の倍数を判定する正規表現の完成形
/^(11(01*00|01*0101)*1|0|(10|11(01*00|01*0101)*01*01(1|00))((0|11)(1|00)|(10|(0|11)01)(01*00|01*0101)*01*01(1|00))*(10|(0|11)01)(01*00|01*0101)*1)+$/;
これが完成形です。試しに検証してみましょう。
const reg = /^(11(01*00|01*0101)*1|0|(10|11(01*00|01*0101)*01*01(1|00))((0|11)(1|00)|(10|(0|11)01)(01*00|01*0101)*01*01(1|00))*(10|(0|11)01)(01*00|01*0101)*1)+$/; console.log('検証スタート'); for (let i = 0; i < 1e6; ++i) { if ((i%7==0) !== reg.test(i.toString(2))) { throw new Error('正規表現で判定できていない数字が見つかりました'); } } console.log('検証終了');
106まで検証してみて、reg.test(n.toString(2))
とn%7 == 0
が等しいことが確認できました。
7進法で7の倍数を判定する正規表現
2進数よりも遷移表が大きくなるぶん複雑になる…と思いきや、めちゃくちゃカンタンな正規表現で書けます。
/0$/
以上です(当たり前)。
おまけ: 0000を受理しないようにする
実は上の正規表現では0000が受理されます。これを受理しないようにしてみます。
const reg = /^((11(01*00|01*0101)*1|(10|11(01*00|01*0101)*01*01(1|00))((0|11)(1|00)|(10|(0|11)01)(01*00|01*0101)*01*01(1|00))*(10|(0|11)01)(01*00|01*0101)*1)(11(01*00|01*0101)*1|0|(10|11(01*00|01*0101)*01*01(1|00))((0|11)(1|00)|(10|(0|11)01)(01*00|01*0101)*01*01(1|00))*(10|(0|11)01)(01*00|01*0101)*1)*|0)$/;
まあほぼ同じです。