ออโตมาตาที่สมบูรณ์
นิยามพื้นฐานของออโตมาตาจำกัดไม่ได้บังคับให้ทุกสถานะต้องมีการเปลี่ยนสถานะสำหรับทุกสัญลักษณ์ ออโตมาตาที่สมบูรณ์ (complete automaton) คือออโตมาตาที่นิยามการเปลี่ยนสถานะจากทุกสถานะสำหรับทุกสัญลักษณ์ของอักษรขาเข้า
วิธีสร้างออโตมาตาที่สมบูรณ์
ให้ออโตมาตา A = ⟨Q, Σ, δ, q0, F⟩ เป็นดังนี้:
ในรูปไม่มีการเปลี่ยนสถานะจากสถานะ q0 สำหรับตัวอักษร “b” ถ้าเกิดกรณีนี้ขึ้น จะถือว่าออโตมาตาไม่ยอมรับสตริงขาเข้านั้น อย่างไรก็ตาม ในแง่ของการเขียนให้เป็นรูปนัย การที่ฟังก์ชันการเปลี่ยนสถานะ δ ไม่นิยามสำหรับบางค่าอาจไม่เหมาะนัก เช่น ในที่นี้ δ(q0, b) ไม่นิยาม
ปัญหานี้แก้ได้ง่ายโดยสร้างออโตมาตาที่สมมูลกันซึ่งมีสถานะเพิ่มขึ้นหนึ่งสถานะ การเปลี่ยนสถานะที่ “ขาดหายไป” ทั้งหมดจะชี้ไปที่สถานะนี้ สถานะนี้ไม่ใช่สถานะสิ้นสุด และขาเข้าที่ตามมาทั้งหมดจะวนอยู่ในสถานะนี้ ออโตมาตาเช่นนี้เรียกว่าออโตมาตาที่สมบูรณ์ ออโตมาตาที่สมมูลกันหลังปรับแล้วอาจมีลักษณะดังนี้:
ได้เพิ่มสถานะ qfail เข้าไป จากสถานะอื่น ๆ ลากการเปลี่ยนสถานะมาที่สถานะนี้ก็ต่อเมื่อเดิมไม่มีการเปลี่ยนสถานะนั้น สถานะนี้ไม่ใช่สถานะสิ้นสุด และวนอยู่กับที่สำหรับขาเข้าทุกตัวที่ตามมา ดังนั้นในกรณีที่ออโตมาตาเดิมพบการเปลี่ยนสถานะที่ขาดหายไป ออโตมาตาใหม่ไม่มีการเปลี่ยนสถานะที่ขาดหายไปเลย แต่จะไปอยู่ที่สถานะ qfail แทน
ดังนั้นโดยไม่เสียนัยทั่วไป จึงสมมติได้เสมอว่าออโตมาตามีการเปลี่ยนสถานะที่นิยามไว้สำหรับทุกคู่ของสถานะและสัญลักษณ์ในอักษร
นิยาม
สำหรับออโตมาตาที่สมบูรณ์ A = ⟨Q, Σ, δ, q0, F⟩ จะได้ว่า
แหล่งอ้างอิง
สารบัญ: ออโตมาตาจำกัด, ออโตมาตาที่สมบูรณ์, ออโตมาตาจำกัดแบบนอนดีเทอร์มินิสติก, การจำลองออโตมาตาแบบนอนดีเทอร์มินิสติก, การแปลง NFA เป็น DFA