↑この記事について、「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('検証終了');

10⁶まで検証してみて、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)$/;

まあほぼ同じです。

Panda Noir

JavaScript の限界を究めるブログでした。最近はいろんな分野を幅広めに書いてます。

「7」の倍数を表す正規表現の解説