ออโตมาตาจำกัดแบบนอนดีเทอร์มินิสติกทั่วไป
ออโตมาตาจำกัดแบบนอนดีเทอร์มินิสติกทั่วไป (generalized nondeterministic finite automaton เรียกย่อว่า GNFA) คือออโตมาตาแบบนอนดีเทอร์มินิสติกที่การเปลี่ยนสถานะไม่จำเป็นต้องมีเฉพาะสัญลักษณ์จากอักษร แต่มีนิพจน์ปรกติกำกับได้
นิยาม
จะใช้ GNFA ในขั้นตอนวิธีการแปลงออโตมาตาจำกัดเป็นนิพจน์ปรกติ ดังนั้น GNFA คือ NFA ที่การเปลี่ยนสถานะนิยามด้วยนิพจน์ปรกติ ตัวอย่างของ GNFA:
จะเห็นว่า เช่น จากสถานะ q2 มีการเปลี่ยนสถานะไปที่สถานะ qf ซึ่งกำกับด้วยนิพจน์ปรกติ a∗ b เงื่อนไขอื่นของ GNFA:
- สถานะเริ่มต้น q0 ต้องมีการเปลี่ยนสถานะไปยังสถานะอื่นทุกสถานะ ในรูปจะเห็นว่าจากสถานะ q0 มีการเปลี่ยนสถานะไปยังสถานะอื่นทุกสถานะ
- GNFA มีสถานะสิ้นสุดเพียงสถานะเดียว และสถานะอื่นทุกสถานะมีการเปลี่ยนสถานะไปยังสถานะนี้ ดังที่เห็นในรูป ทุกสถานะมีลูกศรชี้ไปที่ qf
- สถานะเริ่มต้นต้องไม่เป็นสถานะเดียวกับสถานะสิ้นสุด ดังนั้น GNFA มีอย่างน้อยสองสถานะ
- สถานะอื่นทุกสถานะ ยกเว้นสถานะเริ่มต้นและสถานะสิ้นสุด ต้องมีการเปลี่ยนสถานะไปยังสถานะอื่นทุกสถานะ ยกเว้นสถานะเริ่มต้นและสถานะสิ้นสุด รวมทั้งวงวน (การเปลี่ยนสถานะจากสถานะ qi ไปยังสถานะ qi เดิม)
การแปลง NFA ทั่วไปเป็น GNFA
ถ้ามี NFA อยู่แล้ว การแปลงเป็น GNFA ทำได้ง่าย
- สร้างสถานะเริ่มต้นใหม่ qs และสร้างการเปลี่ยนสถานะแบบเอปไซลอนไปยังสถานะเริ่มต้นเดิม
- สร้างสถานะสิ้นสุดใหม่ qf และลากการเปลี่ยนสถานะแบบเอปไซลอนจากสถานะสิ้นสุดเดิมทุกสถานะไปยังสถานะ qf แล้วเปลี่ยนสถานะสิ้นสุดเดิมให้เป็นสถานะธรรมดา
- ถ้ามีการเปลี่ยนสถานะหลายเส้นที่ใด (เช่น ถ้าจากสถานะ q1 ไปถึงสถานะ q2 ได้ทั้งด้วยสัญลักษณ์ 0 และด้วยสัญลักษณ์ 1) ให้รวมกฎเหล่านี้เป็นนิพจน์ปรกติเดียว โดยเชื่อมสัญลักษณ์เดิมทั้งหมดด้วยตัวดำเนินการยูเนียน (นั่นคือ กำกับลูกศรด้วยนิพจน์ปรกติ 0|1)
- ถ้าออโตมาตาขาดการเปลี่ยนสถานะที่ควรมีตามนิยาม ให้สร้างการเปลี่ยนสถานะนั้นแล้วกำกับด้วยนิพจน์ปรกติ ∅ วิธีนี้ไม่เปลี่ยนภาษาที่ออโตมาตายอมรับ เพราะการเปลี่ยนสถานะเช่นนี้ไม่มีวันเกิดขึ้น
ออโตมาตานี้ใช้แปลงออโตมาตาเป็นนิพจน์ปรกติได้
สารบัญ: นิพจน์ปรกติ, การแปลงนิพจน์ปรกติเป็นออโตมาตา, ออโตมาตาจำกัดแบบนอนดีเทอร์มินิสติกทั่วไป, การแปลงออโตมาตาเป็นนิพจน์ปรกติ