PythonでDFAを使って2進数文字列が3の倍数かどうかを判定する方法

はじめに

ある数の2進表現を配列 n として受け取り、その値が3で割り切れるかどうかを「決定性有限オートマトン(DFA)」を使って判定する問題を考えてみましょう。

例えば、入力が n = [1, 1, 0, 0](10進数の12に相当)であれば、12は3の倍数なので出力は True になります。

DFAによるアプローチ

この問題は、次のようなDFAを構築することで解けます。

考え方はシンプルです。ある数が3で割り切れるとき余りは0になり、割り切れない場合は余りが1または2になります。そこで、これら3つの余り(0・1・2)に対応する3つの状態を用意します。初期状態は余り0を表すため、同時に受理状態(最終状態)にもなります。すべての桁を読み終えた時点で状態が0に戻っていれば、その数は3の倍数であると判断できるのです。

なぜこの遷移でうまくいくのかというと、2進数を左から右へ1桁ずつ読み込むたびに、それまでの値 v は「v × 2 + b」(bは新しく読み込んだビット)へと更新されるからです。したがって、現在の余りを r とすると、新しい余りは (2r + b) mod 3 で求められます。

状態遷移をまとめると以下のようになります。

• 状態0(余り0):入力が0なら状態0のまま、入力が1なら状態1へ
• 状態1(余り1):入力が0なら状態2へ、入力が1なら状態0へ
• 状態2(余り2):入力が0なら状態1へ、入力が1なら状態2のまま

アルゴリズムの手順

解決のための手順は以下の通りです。

1. dfa_state を 0 で初期化する
2. nums の各桁について以下を繰り返す
   • dfa_state == 0 の場合:digit が 1 なら dfa_state を 1 に更新
   • dfa_state == 1 の場合:digit が 0 なら dfa_state を 2 に、1 なら 0 に更新
   • dfa_state == 2 の場合:digit が 0 なら dfa_state を 1 に更新(1なら2のまま)
3. すべての桁を処理した後、dfa_state が 0 なら True を返す
4. そうでなければ False を返す

実装例

理解を深めるために、実際のPythonコードを見てみましょう。

def solve(nums):
    dfa_state = 0
    for digit in nums:
        if dfa_state == 0:
            if digit == 1:
                dfa_state = 1
        elif dfa_state == 1:
            if digit == 0:
                dfa_state = 2
            else:
                dfa_state = 0
        elif dfa_state == 2:
            if digit == 0:
                dfa_state = 1
    return dfa_state == 0

n = [1, 1, 0, 0]
print(solve(n))

入力

[1, 1, 0, 0]

出力

True

まとめ

このように、DFAの状態を「3で割った余り」に対応させることで、除算を行わずに2進数が3の倍数かどうかを効率的に判定できます。各ビットの読み込みごとに状態遷移を1回行うだけなので、計算量は O(n) となり、非常にシンプルかつ高速な手法です。2進数の性質を活かした状態遷移の設計は、オートマトン理論を実践的に学ぶ良い題材といえるでしょう。