การจำลองออโตมาตาแบบนอนดีเทอร์มินิสติก
ถ้ามีออโตมาตาแบบนอนดีเทอร์มินิสติกและต้องการทราบว่ายอมรับสตริงที่กำหนดหรือไม่ อาจแปลงออโตมาตาเป็นแบบดีเทอร์มินิสติก อาจลองดูด้วยวิธีใดวิธีหนึ่ง หรืออาจใช้ขั้นตอนวิธี (อัลกอริทึม) ที่จำลองการทำงานของ NFA
หลักการของขั้นตอนวิธี
จะแสดงหลักการด้วยตัวอย่างที่เหมาะสม ให้ออโตมาตาเป็นดังนี้:
ออโตมาตานี้เป็นออโตมาตาจำกัดแบบนอนดีเทอร์มินิสติกที่ยอมรับภาษาหนึ่ง ในตอนนี้ไม่จำเป็นต้องสนใจว่าเป็นภาษาใด จะแสดงว่าการคำนวณของออโตมาตานี้สำหรับสตริงขาเข้า 11001 มีลักษณะอย่างไร แนวคิดคือ อ่านสัญลักษณ์จากสตริงหนึ่งตัว แล้วดูว่าการเปลี่ยนสถานะหลายเส้นสำหรับสัญลักษณ์เดียวกันพาไปที่ใดได้บ้าง จำสถานะเหล่านั้นไว้ทั้งหมด ในขั้นต่อไปจะถือว่า “อยู่ในทุกสถานะเหล่านี้พร้อมกัน” แล้วพิจารณาว่าจากสถานะเหล่านี้ไปต่อที่ใดได้บ้าง
ดังนั้นจะจำเซตของสถานะที่อาจอยู่ได้ และส่วนของสตริงที่ยังไม่ได้อ่าน ตอนเริ่มต้นมีคู่ ⟨{q0}, 11001⟩ คือเริ่มที่สถานะ q0 (สถานะเริ่มต้น) และสตริงขาเข้าคือ 11001 ออโตมาตามีลักษณะดังนี้ สถานะที่อยู่ในขณะนั้นเน้นด้วยสีแดงและตัวหนา:
สัญลักษณ์แรกคือ 1 จากสถานะ q0 มีการเปลี่ยนสถานะสำหรับสัญลักษณ์ 1 เพียงเส้นเดียว จึงไปถึงสถานะ q1 จำคู่ ⟨{q1}, 1001⟩ ไว้ ออโตมาตามีลักษณะดังนี้:
ทำต่อไป ส่วนของสตริงที่ยังไม่ได้อ่านคือ 1001 จึงหาการเปลี่ยนสถานะสำหรับ 1 อีกครั้ง คราวนี้มีสองเส้น คือกลับไปที่สถานะ q0 และไปที่สถานะ q3 ตอนนี้จะไปทั้งสองสถานะพร้อมกัน จึงจำคู่ ⟨{q0, q3}, 001⟩ ไว้
เหตุผลคืออะไร เรารู้ว่ามีเส้นทางที่ใช้สตริง 11 พาจากสถานะเริ่มต้นไปถึงได้ทั้งสถานะ q3 และสถานะ q0 ตอนนี้ยังไม่รู้ว่ากิ่งใดจะเป็นประโยชน์ จึงจำไว้ทั้งสองกิ่ง ทำต่อไป สัญลักษณ์ขาเข้าคือ 0 ตอนนี้ต้องดูทั้งการเปลี่ยนสถานะจาก q0 และจาก q3 จากสถานะ q0 มีการเปลี่ยนสถานะไปที่สถานะ q1 และ q2 จากสถานะ q3 มีการเปลี่ยนสถานะกลับไปที่ q1 นับรวมสถานะทั้งหมดนี้ จะได้คู่ ⟨{q1, q2}, 01⟩:
แต่ขั้นนี้ยังไม่จบ จะเห็นว่าจากสถานะ q2 มีการเปลี่ยนสถานะแบบเอปไซลอนไปที่สถานะ q4 เรารู้ว่าการเปลี่ยนสถานะแบบเอปไซลอน “ไปได้ทุกเมื่อ” โดยไม่ต้องอ่านอักขระถัดไป กล่าวอีกอย่างคือ โดยไม่ต้องอ่านสัญลักษณ์ถัดไปจากสตริงขาเข้า ยังเปลี่ยนไปที่สถานะ q4 ได้อีก จึงเพิ่มสถานะ q4 เข้าไปในเซตของสถานะที่อาจอยู่ได้: ⟨{q1, q2, q4}, 01⟩ ระบายสีออโตมาตาได้ดังนี้:
ต่อไปขาเข้าคือ 0 ดูว่าจากสามสถานะที่อยู่นั้นเปลี่ยนไปที่ใดได้บ้าง จาก q1 ไปที่ใดไม่ได้ เพราะไม่มีการเปลี่ยนสถานะสำหรับ 0 การคำนวณในกิ่งนี้จึงจบลง จากสถานะ q4 ก็ไปที่ใดไม่ได้เช่นกัน จากสถานะ q2 กลับมาที่สถานะ q2 ได้ และเนื่องจากจากสถานะ q2 มีการเปลี่ยนสถานะแบบเอปไซลอนไปที่สถานะ q4 อีก จึงไปถึงสถานะ q4 ได้ด้วย ดังนั้นจากเซตของสถานะ {q1, q2, q4} สำหรับสัญลักษณ์ 0 จะไปถึงเซตของสถานะ {q2, q4} ได้ จะได้คู่ ⟨{q2, q4}, 1⟩:
สุดท้ายสัญลักษณ์ขาเข้าคือ 1 จากสถานะ q2 ไปที่ใดไม่ได้ การคำนวณในกิ่งนี้จึงจบลง แต่จากสถานะ q4 ไปถึงสถานะ q3 และ q5 ได้ จะได้คู่ ⟨{q3, q5}, ε⟩:
ตอนนี้ออโตมาตาอ่านสตริงครบแล้ว และ “อยู่” ในสองสถานะ คือ q3, q5 เนื่องจากมีอย่างน้อยหนึ่งสถานะที่เป็นสถานะสิ้นสุด ออโตมาตาจึงยอมรับสตริง 11001
ขั้นตอนวิธี
อย่างแรกต้องมีฟังก์ชันที่รับเซตของสถานะเป็นพารามิเตอร์ แล้วคำนวณว่าไปถึงสถานะใดได้อีกบ้างด้วยการเปลี่ยนสถานะแบบเอปไซลอน สิ่งที่ป้อนเข้าคือออโตมาตา ⟨Q, Σ, δ, q0, F⟩ และเซตของสถานะ States สิ่งที่ได้คือซูเปอร์เซตของสถานะเหล่านี้ที่ไปถึงได้ด้วยการเปลี่ยนสถานะแบบเอปไซลอน การดำเนินการนี้เรียกว่าส่วนปิดคลุมเอปไซลอน (ε-closure) ของเซต States
จะใช้ฟังก์ชันนี้ในฟังก์ชันที่จำลองการทำงานของออโตมาตาแบบนอนดีเทอร์มินิสติก สิ่งที่ป้อนเข้าคือออโตมาตา สตริงขาเข้า w = w1w2… wn และเซตของสถานะที่ออโตมาตาอยู่ในขณะนั้น สิ่งที่ได้คือคำตอบ YES หรือ NO ขึ้นอยู่กับว่าออโตมาตายอมรับสตริงที่กำหนดหรือไม่
ถ้าต้องการตรวจสอบว่าออโตมาตายอมรับสตริง w หรือไม่ ให้เรียกใช้ฟังก์ชันดังนี้: ComputeNFA(⟨Q, Σ, δ, q0, F⟩, w, EpsilonClosure(⟨Q, Σ, δ, q0, F⟩, {q0}))
แหล่งอ้างอิง
สารบัญ: ออโตมาตาจำกัด, ออโตมาตาที่สมบูรณ์, ออโตมาตาจำกัดแบบนอนดีเทอร์มินิสติก, การจำลองออโตมาตาแบบนอนดีเทอร์มินิสติก, การแปลง NFA เป็น DFA