✖

การจำลองออโตมาตาแบบนอนดีเทอร์มินิสติก

ถ้ามีออโตมาตาแบบนอนดีเทอร์มินิสติกและต้องการทราบว่ายอมรับสตริงที่กำหนดหรือไม่ อาจแปลงออโตมาตาเป็นแบบดีเทอร์มินิสติก อาจลองดูด้วยวิธีใดวิธีหนึ่ง หรืออาจใช้ขั้นตอนวิธี (อัลกอริทึม) ที่จำลองการทำงานของ 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

FunctionEpsilonClosure(⟨Q,Σ,δ,q0,F⟩,States)NextStates←∅ForEachq∈StatesDoNextStates←NextStates∪{q}∪δ(q,ε)EndForIfNextStates∖States=∅DoReturnStatesElseReturnEpsilonClosure(⟨Q,Σ,δ,q0,F⟩,NextStates)EndIfEndFunction

จะใช้ฟังก์ชันนี้ในฟังก์ชันที่จำลองการทำงานของออโตมาตาแบบนอนดีเทอร์มินิสติก สิ่งที่ป้อนเข้าคือออโตมาตา สตริงขาเข้า w = w1w2… wn และเซตของสถานะที่ออโตมาตาอยู่ในขณะนั้น สิ่งที่ได้คือคำตอบ YES หรือ NO ขึ้นอยู่กับว่าออโตมาตายอมรับสตริงที่กำหนดหรือไม่

FunctionComputeNFA(⟨Q,Σ,δ,q0,F⟩,w,States)Ifw=ϵDoIfStates∩F≠∅DoReturnYESElseReturnNOEndIfEndIfNextStates←∅ForEachq∈StatesDoNextStates←NextStates∪δ(q,w1)EndForNextStates←EpsilonClosure(⟨Q,Σ,δ,q0,F⟩,NextStates)ReturnComputeNFA(⟨Q,Σ,δ,q0,F⟩,w2w3…wn,NextStates)EndFunction

ถ้าต้องการตรวจสอบว่าออโตมาตายอมรับสตริง w หรือไม่ ให้เรียกใช้ฟังก์ชันดังนี้: ComputeNFA(⟨Q, Σ, δ, q0, F⟩, w, EpsilonClosure(⟨Q, Σ, δ, q0, F⟩, {q0}))

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

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