✖

ออโตมาตาที่สมบูรณ์

นิยามพื้นฐานของออโตมาตาจำกัดไม่ได้บังคับให้ทุกสถานะต้องมีการเปลี่ยนสถานะสำหรับทุกสัญลักษณ์ ออโตมาตาที่สมบูรณ์ (complete automaton) คือออโตมาตาที่นิยามการเปลี่ยนสถานะจากทุกสถานะสำหรับทุกสัญลักษณ์ของอักษรขาเข้า

วิธีสร้างออโตมาตาที่สมบูรณ์

ให้ออโตมาตา A = ⟨Q, Σ, δ, q0, F⟩ เป็นดังนี้:

ในรูปไม่มีการเปลี่ยนสถานะจากสถานะ q0 สำหรับตัวอักษร “b” ถ้าเกิดกรณีนี้ขึ้น จะถือว่าออโตมาตาไม่ยอมรับสตริงขาเข้านั้น อย่างไรก็ตาม ในแง่ของการเขียนให้เป็นรูปนัย การที่ฟังก์ชันการเปลี่ยนสถานะ δ ไม่นิยามสำหรับบางค่าอาจไม่เหมาะนัก เช่น ในที่นี้ δ(q0, b) ไม่นิยาม

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

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

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

นิยาม

สำหรับออโตมาตาที่สมบูรณ์ A = ⟨Q, Σ, δ, q0, F⟩ จะได้ว่า

∀q∈Q∀a∈Σ∃r∈Q:δ(q,a)=r

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

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