การแปลง 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 ดังนี้:
หมายความว่าอย่างไร ออโตมาตาแบบนอนดีเทอร์มินิสติกอยู่ได้หลายสถานะพร้อมกัน เช่น อาจเกิดกรณีที่ออโตมาตาแบบนอนดีเทอร์มินิสติกอยู่ในสถานะ {q0, q1} เมื่ออ่านสัญลักษณ์ถัดไป เช่น 1 อาจไปถึงเซตของสถานะ {q0, q2, q3} ในออโตมาตาเดียวกันแบบดีเทอร์มินิสติก จะสร้างสถานะสองสถานะ แล้วตั้งชื่อว่า {q0, q1} และ {q0, q2, q3} และกำหนดการเปลี่ยนสถานะสำหรับสัญลักษณ์ 1 ระหว่างสองสถานะนี้ ในทางรูปนัยจึงเป็นการไปจากสถานะหนึ่งไปยังอีกสถานะหนึ่ง แต่ชื่อของสถานะบอกได้ว่าในออโตมาตาแบบนอนดีเทอร์มินิสติกจะอยู่ในสองสถานะและสามสถานะตามลำดับ
ตัวอย่าง
ให้ออโตมาตาแบบนอนดีเทอร์มินิสติกเป็นดังนี้:
การสร้างออโตมาตาแบบดีเทอร์มินิสติกต้องสร้างฟังก์ชันการเปลี่ยนสถานะใหม่เป็นสำคัญ ตารางที่บันทึกการเปลี่ยนสถานะทั้งหมดจะช่วยในเรื่องนี้ ตอนเริ่มต้นตารางเป็นดังนี้:
เมื่อจบขั้นตอนวิธี หลักซ้ายจะมีสถานะทั้งหมดของออโตมาตาแบบดีเทอร์มินิสติก และตารางที่เติมครบแล้วจะกำหนดฟังก์ชันการเปลี่ยนสถานะ ตอนนี้เขียนลงในตารางว่าถ้าอยู่ในสถานะ {q0} และสัญลักษณ์ขาเข้าคือ 0 และ 1 จะไปถึงสถานะใด
จากสถานะ q0 สำหรับสัญลักษณ์ 0 มีการเปลี่ยนสถานะไปที่สถานะ q1 เท่านั้น ส่วนสำหรับสัญลักษณ์ 1 มีการเปลี่ยนสถานะไปที่สถานะ q1 และ q2 ตอนนี้เพิ่มสถานะใหม่สองสถานะลงในตาราง คือ {q1} และ {q1, q2} เพราะเหตุใด เมื่อใดที่เติมเซตของสถานะที่ยังไม่มีในหลักซ้ายลงในตาราง ก็จะเพิ่มเซตของสถานะนั้นลงในหลักซ้าย
แล้วเติมตารางอีกครั้ง สำหรับสถานะ {q1, q2} ต้องไม่ลืมตรวจทั้งสองสถานะ นั่นคือนำสถานะที่ไปถึงได้จากสถานะ q1 มายูเนียนกับสถานะที่ไปถึงได้จากสถานะ q2
ได้สถานะใหม่หลายสถานะ ซึ่งต้องเพิ่มลงในตาราง:
…แล้วเติมการเปลี่ยนสถานะอีกครั้ง:
สถานะ {q0, q1, q3} {q1} และ {q1,q2} มีอยู่แล้ว จึงเพิ่มเฉพาะสถานะ {q0,q1,q2,q3}
ไม่มีสถานะใหม่เพิ่มขึ้นอีก ตารางจึงเติมครบแล้ว ตอนนี้เหลือเพียงสร้างแผนภาพ สถานะของออโตมาตาแบบดีเทอร์มินิสติกอยู่ในหลักแรก การเปลี่ยนสถานะสำหรับสัญลักษณ์ 0 และ 1 อยู่ในหลักถัดไป ทุกสถานะที่มีสถานะสิ้นสุดของออโตมาตาเดิมอยู่ด้วย จะเป็นสถานะสิ้นสุดในออโตมาตานี้ด้วย นั่นคือทุกสถานะที่มี q3 จะเป็นสถานะสิ้นสุด ออโตมาตาจะมีลักษณะดังนี้:
แสดงได้ว่าออโตมาตานี้ทำงานถูกต้องจริง ลองให้ยอมรับสตริง 11001 ในออโตมาตาแบบดีเทอร์มินิสติกจะเดินตามเส้นทาง
และออโตมาตาจะยอมรับสตริงนี้ เพราะสถานะสุดท้าย {q0, q1, q2, q3} เป็นสถานะสิ้นสุด ในออโตมาตาแบบนอนดีเทอร์มินิสติก ระหว่างการจำลองจะไปถึงสถานะเดียวกัน คือเริ่มที่สถานะ q0 สำหรับสัญลักษณ์ 1 จะไปถึงสถานะ {q1, q2} สัญลักษณ์ 1 ตัวถัดไปจะพาไปที่สถานะ {q0,q3} และเป็นเช่นนี้ต่อไปสำหรับสถานะที่เหลือ สุดท้ายจะอยู่ในทุกสถานะ {q0, q1, q2, q3} และออโตมาตาจะยอมรับสตริงนี้
แหล่งอ้างอิง
สารบัญ: ออโตมาตาจำกัด, ออโตมาตาที่สมบูรณ์, ออโตมาตาจำกัดแบบนอนดีเทอร์มินิสติก, การจำลองออโตมาตาแบบนอนดีเทอร์มินิสติก, การแปลง NFA เป็น DFA