Python에서 DFA를 사용하여 이진 문자열이 3의 배수인지 확인

임의의 숫자의 이진 표현을 나타내는 배열 n이 있다고 가정합니다. Deterministic Finite Automata DFA를 사용하여 이진 표현이 3으로 나눌 수 있는지 여부를 확인해야 합니다.

따라서 입력이 n =[1, 1, 0, 0](12의 이진법)과 같으면 출력은 True가 됩니다.

이를 해결하기 위해 아래와 같이 DFA를 구성할 수 있습니다. -

접근 방식은 숫자가 3으로 나누어 떨어지면 나머지는 0이 되고 그렇지 않으면 나머지는 1 또는 2가 될 때 간단합니다. 이 세 나머지에는 세 가지 상태가 있습니다. 나머지가 0이면 숫자가 나눌 수 있음을 의미하기 때문에 초기 상태도 최종 상태입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• dfa_state :=0
• 0부터 숫자 - 1까지의 범위에 있는 i에 대해
  • 숫자 :=숫자[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이면
  • 참 반환
• 거짓을 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

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