✖

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

ออโตมาตาจำกัดแบบนอนดีเทอร์มินิสติกทั่วไป (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 ทำได้ง่าย

  1. สร้างสถานะเริ่มต้นใหม่ qs และสร้างการเปลี่ยนสถานะแบบเอปไซลอนไปยังสถานะเริ่มต้นเดิม
  2. สร้างสถานะสิ้นสุดใหม่ qf และลากการเปลี่ยนสถานะแบบเอปไซลอนจากสถานะสิ้นสุดเดิมทุกสถานะไปยังสถานะ qf แล้วเปลี่ยนสถานะสิ้นสุดเดิมให้เป็นสถานะธรรมดา
  3. ถ้ามีการเปลี่ยนสถานะหลายเส้นที่ใด (เช่น ถ้าจากสถานะ q1 ไปถึงสถานะ q2 ได้ทั้งด้วยสัญลักษณ์ 0 และด้วยสัญลักษณ์ 1) ให้รวมกฎเหล่านี้เป็นนิพจน์ปรกติเดียว โดยเชื่อมสัญลักษณ์เดิมทั้งหมดด้วยตัวดำเนินการยูเนียน (นั่นคือ กำกับลูกศรด้วยนิพจน์ปรกติ 0|1)
  4. ถ้าออโตมาตาขาดการเปลี่ยนสถานะที่ควรมีตามนิยาม ให้สร้างการเปลี่ยนสถานะนั้นแล้วกำกับด้วยนิพจน์ปรกติ ∅ วิธีนี้ไม่เปลี่ยนภาษาที่ออโตมาตายอมรับ เพราะการเปลี่ยนสถานะเช่นนี้ไม่มีวันเกิดขึ้น

ออโตมาตานี้ใช้แปลงออโตมาตาเป็นนิพจน์ปรกติได้

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