✖

การแปลง NFA เป็น DFA

บทความนี้จะแสดงวิธีแปลงออโตมาตาแบบนอนดีเทอร์มินิสติกเป็นออโตมาตาแบบดีเทอร์มินิสติก ซึ่งเป็นการพิสูจน์ว่าความสามารถในการคำนวณ (computational power) ของออโตมาตาแบบนอนดีเทอร์มินิสติกและแบบดีเทอร์มินิสติกเท่ากัน

แนวคิดหลัก

ให้ออโตมาตาแบบนอนดีเทอร์มินิสติก ⟨QN, ΣN, δN, q0, FN⟩ ไม่มีการเปลี่ยนสถานะแบบเอปไซลอน สร้างออโตมาตาแบบดีเทอร์มินิสติก ⟨QD, ΣD, δD, p0, FD⟩ โดยให้

  • QD ⊆ 2QN
  • ΣD = ΣN
  • p0 = {q0}
  • FD = {Q ∈ QD | Q ∩ FN ≠ ∅}

นิยามฟังก์ชันการเปลี่ยนสถานะ δD ดังนี้:

∀Q∈QD,a∈ΣD:δD(Q,a)=⋃q∈QδN(q,a)

หมายความว่าอย่างไร ออโตมาตาแบบนอนดีเทอร์มินิสติกอยู่ได้หลายสถานะพร้อมกัน เช่น อาจเกิดกรณีที่ออโตมาตาแบบนอนดีเทอร์มินิสติกอยู่ในสถานะ {q0, q1} เมื่ออ่านสัญลักษณ์ถัดไป เช่น 1 อาจไปถึงเซตของสถานะ {q0, q2, q3} ในออโตมาตาเดียวกันแบบดีเทอร์มินิสติก จะสร้างสถานะสองสถานะ แล้วตั้งชื่อว่า {q0, q1} และ {q0, q2, q3} และกำหนดการเปลี่ยนสถานะสำหรับสัญลักษณ์ 1 ระหว่างสองสถานะนี้ ในทางรูปนัยจึงเป็นการไปจากสถานะหนึ่งไปยังอีกสถานะหนึ่ง แต่ชื่อของสถานะบอกได้ว่าในออโตมาตาแบบนอนดีเทอร์มินิสติกจะอยู่ในสองสถานะและสามสถานะตามลำดับ

ตัวอย่าง

ให้ออโตมาตาแบบนอนดีเทอร์มินิสติกเป็นดังนี้:

การสร้างออโตมาตาแบบดีเทอร์มินิสติกต้องสร้างฟังก์ชันการเปลี่ยนสถานะใหม่เป็นสำคัญ ตารางที่บันทึกการเปลี่ยนสถานะทั้งหมดจะช่วยในเรื่องนี้ ตอนเริ่มต้นตารางเป็นดังนี้:

สถานะ/สัญลักษณ์01{q0}

เมื่อจบขั้นตอนวิธี หลักซ้ายจะมีสถานะทั้งหมดของออโตมาตาแบบดีเทอร์มินิสติก และตารางที่เติมครบแล้วจะกำหนดฟังก์ชันการเปลี่ยนสถานะ ตอนนี้เขียนลงในตารางว่าถ้าอยู่ในสถานะ {q0} และสัญลักษณ์ขาเข้าคือ 0 และ 1 จะไปถึงสถานะใด

สถานะ/สัญลักษณ์01{q0}{q1}{q1,q2}

จากสถานะ q0 สำหรับสัญลักษณ์ 0 มีการเปลี่ยนสถานะไปที่สถานะ q1 เท่านั้น ส่วนสำหรับสัญลักษณ์ 1 มีการเปลี่ยนสถานะไปที่สถานะ q1 และ q2 ตอนนี้เพิ่มสถานะใหม่สองสถานะลงในตาราง คือ {q1} และ {q1, q2} เพราะเหตุใด เมื่อใดที่เติมเซตของสถานะที่ยังไม่มีในหลักซ้ายลงในตาราง ก็จะเพิ่มเซตของสถานะนั้นลงในหลักซ้าย

สถานะ/สัญลักษณ์01{q0}{q1}{q1,q2}{q1}{q1,q2}

แล้วเติมตารางอีกครั้ง สำหรับสถานะ {q1, q2} ต้องไม่ลืมตรวจทั้งสองสถานะ นั่นคือนำสถานะที่ไปถึงได้จากสถานะ q1 มายูเนียนกับสถานะที่ไปถึงได้จากสถานะ q2

สถานะ/สัญลักษณ์01{q0}{q1}{q1,q2}{q1}{q0,q1,q3}{q0,q3}{q1,q2}{q0,q1,q3}{q0,q3}

ได้สถานะใหม่หลายสถานะ ซึ่งต้องเพิ่มลงในตาราง:

สถานะ/สัญลักษณ์01{q0}{q1}{q1,q2}{q1}{q0,q1,q3}{q0,q3}{q1,q2}{q0,q1,q3}{q0,q3}{q0,q1,q3}{q0,q3}

…แล้วเติมการเปลี่ยนสถานะอีกครั้ง:

สถานะ/สัญลักษณ์01{q0}{q1}{q1,q2}{q1}{q0,q1,q3}{q0,q3}{q1,q2}{q0,q1,q3}{q0,q3}{q0,q1,q3}{q0,q1,q3}{q0,q1,q2,q3}{q0,q3}{q1}{q1,q2}

สถานะ {q0, q1, q3} {q1} และ {q1,q2} มีอยู่แล้ว จึงเพิ่มเฉพาะสถานะ {q0,q1,q2,q3}

สถานะ/สัญลักษณ์01{q0}{q1}{q1,q2}{q1}{q0,q1,q3}{q0,q3}{q1,q2}{q0,q1,q3}{q0,q3}{q0,q1,q3}{q0,q1,q3}{q0,q1,q2,q3}{q0,q3}{q1}{q1,q2}{q0,q1,q2,q3}{q0,q1,q3}{q0,q1,q2,q3}

ไม่มีสถานะใหม่เพิ่มขึ้นอีก ตารางจึงเติมครบแล้ว ตอนนี้เหลือเพียงสร้างแผนภาพ สถานะของออโตมาตาแบบดีเทอร์มินิสติกอยู่ในหลักแรก การเปลี่ยนสถานะสำหรับสัญลักษณ์ 0 และ 1 อยู่ในหลักถัดไป ทุกสถานะที่มีสถานะสิ้นสุดของออโตมาตาเดิมอยู่ด้วย จะเป็นสถานะสิ้นสุดในออโตมาตานี้ด้วย นั่นคือทุกสถานะที่มี q3 จะเป็นสถานะสิ้นสุด ออโตมาตาจะมีลักษณะดังนี้:

แสดงได้ว่าออโตมาตานี้ทำงานถูกต้องจริง ลองให้ยอมรับสตริง 11001 ในออโตมาตาแบบดีเทอร์มินิสติกจะเดินตามเส้นทาง

q0→1q1,q2→1q0,q3→0q1→0q0,q1,q3→1q0,q1,q2,q3

และออโตมาตาจะยอมรับสตริงนี้ เพราะสถานะสุดท้าย {q0, q1, q2, q3} เป็นสถานะสิ้นสุด ในออโตมาตาแบบนอนดีเทอร์มินิสติก ระหว่างการจำลองจะไปถึงสถานะเดียวกัน คือเริ่มที่สถานะ q0 สำหรับสัญลักษณ์ 1 จะไปถึงสถานะ {q1, q2} สัญลักษณ์ 1 ตัวถัดไปจะพาไปที่สถานะ {q0,q3} และเป็นเช่นนี้ต่อไปสำหรับสถานะที่เหลือ สุดท้ายจะอยู่ในทุกสถานะ {q0, q1, q2, q3} และออโตมาตาจะยอมรับสตริงนี้

แหล่งอ้างอิง

สารบัญ: ออโตมาตาจำกัด, ออโตมาตาที่สมบูรณ์, ออโตมาตาจำกัดแบบนอนดีเทอร์มินิสติก, การจำลองออโตมาตาแบบนอนดีเทอร์มินิสติก, การแปลง NFA เป็น DFA