ตรวจสอบว่าสตริงไบนารีทวีคูณ 3 โดยใช้ DFA ใน Python

สมมติว่าเรามีอาร์เรย์ n ที่แทนเลขฐานสองของตัวเลขใดๆ เราต้องตรวจสอบว่าการแทนค่าไบนารีของมันถูกหารด้วยสามหรือไม่โดยใช้ Deterministic Finite Automata DFA

ดังนั้น หากอินพุตเป็น n =[1, 1, 0, 0] (ไบนารีของ 12) เอาต์พุตจะเป็น True

เพื่อแก้ปัญหานี้ เราสามารถสร้าง DFA ได้ดังนี้ -

วิธีการนั้นง่ายเมื่อตัวเลขหารด้วย 3 ลงตัวแล้ว เศษที่เหลือจะเป็น 0 ถ้าไม่ใช่ เศษที่เหลือจะเป็น 1 หรือ 2 มีสามสถานะสำหรับสามเศษที่เหลือ สถานะเริ่มต้นก็เป็นสถานะสุดท้ายเช่นกันเพราะเมื่อส่วนที่เหลือเป็น 0 หมายความว่าตัวเลขนั้นหารลงตัว

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• dfa_state :=0
• สำหรับฉันในช่วง 0 ถึงขนาดของ nums - 1 ทำ
  • หลัก :=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
• คืนค่าเท็จ

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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