✖

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

ออโตมาตาจำกัดที่กล่าวถึงในบทก่อน ๆ (เรียกย่อว่า FA หรือ DFA) เป็นแบบดีเทอร์มินิสติกเสมอ กล่าวคือ ในทุกขณะรู้แน่ชัดว่าออโตมาตาจะทำอะไร ต่อไปจะพิจารณาแนวคิดที่กว้างกว่า คือออโตมาตาจำกัดแบบนอนดีเทอร์มินิสติก (nondeterministic finite automaton เรียกย่อว่า NFA) ซึ่งอาจมีการเปลี่ยนสถานะหลายเส้นที่ออกจากสถานะเดียวกันสำหรับสัญลักษณ์เดียวกัน

ตัวอย่าง

พิจารณาแผนภาพของออโตมาตาต่อไปนี้:

ออโตมาตานี้แปลกตรงไหน ตรงที่จากปม q0 มีเส้นเชื่อมสองเส้นสำหรับสัญลักษณ์ 0 ถ้าลองให้ยอมรับสตริง 001 ดูเหมือนว่าออโตมาตาจะไม่รู้ว่าควรอยู่ที่สถานะ q0 หรือควรเปลี่ยนไปที่ q1 ออโตมาตาเช่นนี้เป็นแบบนอนดีเทอร์มินิสติก

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

แล้วออโตมาตาจะตัดสินใจอย่างไร ออโตมาตาแบบนอนดีเทอร์มินิสติกจะเลือก (บางครั้งพูดว่า “เดา”) การเปลี่ยนสถานะที่นำไปสู่การยอมรับสตริงเสมอ ถ้าทำได้

ถ้าป้อนสตริง 001 เข้าไปในออโตมาตา ออโตมาตามีทางเลือกในการจัดการกับสตริงดังนี้:

q0→q0→q0→q0q0→q0→q1→q2

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

ออโตมาตาเลือกกิ่งที่ “เป็นประโยชน์” ได้เองอย่างไร อาจนึกภาพว่าออโตมาตาแบบนอนดีเทอร์มินิสติกไล่ดูทุกกิ่งที่เป็นไปได้ ถ้าพบกิ่งที่ยอมรับสตริง ก็จะยอมรับสตริงนั้น แล้วจะไล่ดูทุกกิ่งได้อย่างไร กล่าวง่าย ๆ คือ เมื่ออยู่ที่สถานะที่มีเส้นเชื่อม n เส้นสำหรับสัญลักษณ์ปัจจุบัน ออโตมาตาจะทำสำเนาตัวเอง n ชุด และแต่ละชุดเดินไปคนละทาง ด้วยวิธีนี้จึงไล่ดูทุกทางเลือกได้ทีละขั้น

ต้นไม้การคำนวณ

ปรับออโตมาตาก่อนหน้าเล็กน้อย:

ความเป็นนอนดีเทอร์มินิสติกยังคงอยู่ที่สถานะแรก ออโตมาตาก่อนหน้ายอมรับสตริงทั้งหมดที่ลงท้ายด้วย 01 ส่วนออโตมาตาที่ปรับแล้วนี้ยอมรับสตริงทั้งหมดที่มีสตริงย่อย 01 เช่น ยอมรับสตริง 101 หรือ 0101 กิ่งของการคำนวณทั้งหมดแสดงเป็นภาพได้ง่าย ๆ ด้วยต้นไม้ (computation tree) เช่น สำหรับสตริง 01010 ต้นไม้อาจมีลักษณะดังนี้:

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

สังเกตว่ามีกิ่งทั้งหมดสองกิ่งที่จบที่สถานะ q2 ซึ่งเป็นสถานะสิ้นสุด แสดงว่ามีกิ่งของการคำนวณสองกิ่งที่ทำให้ออโตมาตายอมรับสตริงที่กำหนดได้ ดังนั้นออโตมาตานี้ยอมรับสตริง 01010 ลองสร้างต้นไม้ทำนองเดียวกันสำหรับสตริง 1000

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

การเปลี่ยนสถานะแบบเอปไซลอน

ในออโตมาตาแบบนอนดีเทอร์มินิสติกยังใช้การเปลี่ยนสถานะแบบเอปไซลอน (ε-transition) ได้อีกด้วย การเปลี่ยนสถานะแบบนี้ทำได้ไม่ว่าขาเข้าจะเป็นสัญลักษณ์ใด และไม่ต้องอ่านสัญลักษณ์ใดจากสตริงเลย จะเขียนออโตมาตาแบบนอนดีเทอร์มินิสติกที่ยอมรับสตริงว่าง สตริงทั้งหมดที่ประกอบด้วยเลข 1 เท่านั้น และสตริงในรูป (10)n คือ 10, 1010, … ได้อย่างไร

ได้แบ่งออโตมาตาเป็น “ออโตมาตาย่อย” สองส่วน ส่วนบนทำหน้าที่จำแนกสตริงที่ประกอบด้วยเลข 1 ส่วนล่างทำหน้าที่จำแนกสตริงในรูป (10)n ลองให้ยอมรับสตริง 111 ตอนเริ่มต้นออโตมาตาอยู่ที่สถานะ q0 และสตริงขาเข้าคือ 111 เนื่องจากมีการเปลี่ยนสถานะแบบเอปไซลอนให้ใช้ ออโตมาตาจึงเลือกเปลี่ยนไปที่สถานะ q1 หรือ q2 ได้ตามที่เหมาะ จะเห็นว่าควรเปลี่ยนไปที่สถานะ q1 ออโตมาตาจึงเปลี่ยนไปที่นั่น ขณะนั้นสตริงขาเข้ายังคงเป็น 111 อยู่ จากนั้นออโตมาตาจึงเริ่มอ่านสัญลักษณ์จากสตริงและเปลี่ยนจากสถานะ q1 ไปที่ q1 เดิม จนอ่านสตริงครบและยอมรับสตริงนั้น

ถ้าลองให้ยอมรับ 1010 ตอนเริ่มต้นออโตมาตาจะเปลี่ยนไปที่สถานะ q2 แล้วจึงเริ่มอ่านสัญลักษณ์จากที่นั่น และยอมรับสตริงได้เช่นกัน

สำหรับสตริง 1100 ไม่ว่าออโตมาตาจะทำอย่างไร ก็ไม่มีทางยอมรับสตริงนี้ได้

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

และ

แล้วสร้างออโตมาตาจำกัดแบบดีเทอร์มินิสติกที่ยอมรับยูเนียนของภาษาทั้งสอง เมื่อใช้การเปลี่ยนสถานะแบบเอปไซลอน จะสร้างออโตมาตาเช่นนั้นได้ดังนี้:

เพียงเพิ่มสถานะเริ่มต้นใหม่ ซึ่งมีการเปลี่ยนสถานะแบบเอปไซลอนสองเส้นไปยังสถานะเริ่มต้นเดิมของออโตมาตาเดิมทั้งสอง แค่นั้นก็เสร็จ ออโตมาตาจะตัดสินใจแบบนอนดีเทอร์มินิสติกว่าจะลองให้ “ออโตมาตาย่อย” ตัวใดยอมรับสตริง

นิยามของออโตมาตาแบบนอนดีเทอร์มินิสติก

ได้เห็นแล้วว่าออโตมาตาจำกัดแบบดีเทอร์มินิสติกและแบบนอนดีเทอร์มินิสติกต่างกันอย่างไร เหลือเพียงเขียนให้เป็นรูปนัย ออโตมาตาจำกัดแบบดีเทอร์มินิสติกนิยามเป็นสิ่งอันดับ 5 สิ่ง ⟨Q, Σ, δ, q0, F⟩ โดยที่ Q เป็นเซตของสถานะ Σ เป็นอักษร δ เป็นฟังก์ชันการเปลี่ยนสถานะ q0 เป็นสถานะเริ่มต้น และ F เป็นเซตของสถานะสิ้นสุด สิ่งเดียวที่เปลี่ยนในนิยามของออโตมาตาแบบนอนดีเทอร์มินิสติกคือนิยามของฟังก์ชันการเปลี่ยนสถานะ

ในแบบดีเทอร์มินิสติก เมื่อเรียกใช้ δ(q, w) ฟังก์ชันจะคืนค่าได้เพียงสถานะเดียว ส่วนในแบบนอนดีเทอร์มินิสติก ฟังก์ชันคืนค่าได้หลายสถานะ ถ้ามีการเปลี่ยนสถานะหลายเส้นสำหรับสัญลักษณ์เดียว เนื่องจากต้องนิยามการเปลี่ยนสถานะแบบเอปไซลอนด้วย จึงให้เซต Σ ∪ {ε} เขียนแทนด้วย Σε นั่นคือ Σε = Σ ∪ {ε} จึงนิยามฟังก์ชัน δ เป็น

δ:Q×Σε→2Q

2Q แทนเพาเวอร์เซต คือเซตของสับเซตทั้งหมดของเซต Q การคำนวณในรูปนัยคล้ายกับของออโตมาตาจำกัดมาก รูปแบบของออโตมาตายังคงเป็นคู่อันดับ ⟨q, w⟩ ∈ Q × Σ∗ ขั้นของการคำนวณ ↦ เป็นความสัมพันธ์บนเซตของรูปแบบ ซึ่ง

⟨qi,w0w1…wn⟩↦⟨qj,w1…wn⟩

ก็ต่อเมื่อ qj ∈ δ(qi, w0) ประโยคนี้คือจุดที่ต่างกันมากที่สุด ในออโตมาตาแบบดีเทอร์มินิสติก เงื่อนไขนี้เขียนเป็น qj = δ(qi, w0) เพราะฟังก์ชัน δ คืนค่าเป็นสถานะเดียวเสมอ ส่วนฟังก์ชันการเปลี่ยนสถานะแบบนอนดีเทอร์มินิสติกคืนค่าเป็นเซตของสถานะ จึงใช้สัญลักษณ์ ∈ ส่วนปิดคลุมสะท้อนและถ่ายทอดของความสัมพันธ์ยังคงเขียนแทนด้วย ↦ ∗ ออโตมาตายอมรับสตริง w ก็ต่อเมื่อมี qf ∈ F ที่ทำให้

⟨q0,w⟩↦∗⟨qf,ε⟩

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

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