PythonでDFAを使用して、バイナリ文字列が3の倍数であるかどうかを確認します

任意の数のバイナリ表現を表す配列nがあるとします。 Deterministic Finite Automata DFAを使用して、そのバイナリ表現が3で割り切れるかどうかを確認する必要があります。

したがって、入力がn =[1、1、0、0]（12のバイナリ）のような場合、出力はTrueになります。

これを解決するために、以下のようにDFAを構築できます-

数値が3で割り切れる場合、余りは0になり、そうでない場合、余りは1または2になります。これらの3つの余りには、3つの状態があります。余りが0の場合、数値が除算可能であることを意味するため、初期状態も最終状態です。

これを解決するには、次の手順に従います-

• dfa_state：=0
• 範囲0からnums-1のサイズのiの場合、do
  • 桁：=nums [i]
  • dfa_stateが0の場合、
    • 数字が1と同じ場合、
      • dfa_state：=1
  • それ以外の場合、dfa_stateが1の場合、
    • 数字が0と同じ場合、
      • dfa_state：=2
    • それ以外の場合、
      • dfa_state：=0
  • それ以外の場合、dfa_stateが2の場合、
    • 数字が0と同じ場合、
      • dfa_state：=1
• dfa_stateが0の場合、
  • Trueを返す
• Falseを返す

理解を深めるために、次の実装を見てみましょう-

例

def solve(nums):
   dfa_state = 0
   for i in range(len(nums)):
      digit = nums[i]
      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
            if dfa_state == 0:
               return True
   return False
n = [1, 1, 0, 0]
print(solve(n))

入力

[1, 1, 0, 0]

出力

True