สถานะที่ไม่จำเป็น
ออโตมาตาจำกัดอาจมีสถานะที่ไม่สามารถไปถึงสถานะสิ้นสุดได้เลย สถานะเหล่านี้จึงไม่มีประโยชน์ และเรียกว่าสถานะที่ไม่จำเป็น (redundant state) โดยทั่วไปต้องการกำจัดสถานะเหล่านี้ออก เพราะทำให้ออโตมาตาซับซ้อนขึ้นโดยไม่จำเป็น
ตัวอย่างของสถานะที่ไม่จำเป็น
ให้ออโตมาตาจำกัดเป็นดังนี้:
จะเห็นว่าเมื่อไปถึงสถานะ q4 หรือ q5 แล้ว จะไม่มีทางไปถึงสถานะสิ้นสุด q1 หรือ q2 ได้อีกเลย สถานะเหล่านี้จึงไม่จำเป็นและกำจัดออกได้เลย ซึ่งจะได้ออโตมาตาใหม่ที่สมมูลกับออโตมาตาเดิม คือยอมรับภาษาเดียวกัน หลังลบสถานะที่ไม่จำเป็นแล้ว ออโตมาตาจะมีลักษณะดังนี้:
ออโตมาตานี้ยอมรับภาษาเดียวกัน อย่างไรก็ตาม บางครั้งการมีสถานะที่ไม่จำเป็นก็เป็นประโยชน์ เช่น เมื่อสร้างออโตมาตาที่สมบูรณ์
นิยามของสถานะที่ไม่จำเป็น
ให้ออโตมาตาจำกัด A = ⟨Q, Σ, δ, q0, F⟩ สถานะ q ∈ Q เป็นสถานะที่ไม่จำเป็น ถ้าไม่มีสตริง w ∈ Σ∗ และไม่มีสถานะ qf ∈ F ใดที่ทำให้
วิธีกำจัดสถานะที่ไม่จำเป็น
สมมติว่าออโตมาตา A = ⟨Q, Σ, δ, q0, F⟩ ที่ป้อนเข้าไม่มีสถานะที่ไปไม่ถึงแล้ว จะหาสถานะที่นำไปสู่สถานะสิ้นสุดทีละขั้น แล้วหาสถานะที่นำไปสู่สถานะที่นำไปสู่สถานะสิ้นสุด และทำเช่นนี้ซ้ำไปเรื่อย ๆ จะได้เซตของสถานะทั้งหมดที่ไม่ใช่สถานะที่ไม่จำเป็น เริ่มต้นให้ S0 = F แล้วสร้างเซต Si ถัดไปสำหรับ i ∈ ℕ ตามกฎนี้:
เซตที่ได้ของสถานะทั้งหมดที่ไม่ใช่สถานะที่ไม่จำเป็นเขียนได้ดังนี้:
และเซตของสถานะที่ไม่จำเป็นเขียนได้เป็น
กล่าวอีกอย่างคือ ถ้า Si = Si + 1 แล้วเซต Q ∖ Si คือเซตของสถานะที่ไม่จำเป็น จะแสดงขั้นตอนด้วยออโตมาตานี้:
อย่างแรกให้ S0 = {q1, q2} ต่อไปสร้างเซต S1 โดยเพิ่มทุกสถานะที่นำไปสู่สถานะใดสถานะหนึ่งในเซต S0 เข้าไปในเซต S0 จึงเพิ่มสถานะ q0 และ q3 เพราะจาก q0 มีการเปลี่ยนสถานะไปที่ q1 และจาก q3 มีการเปลี่ยนสถานะไปที่ q2 จะได้ S1 = {q0, q1, q2, q3} เนื่องจาก S0 ≠ S1 จึงทำต่อไป
สร้างเซต S2 หาสถานะทั้งหมดที่ไปถึง S1 ได้และยังไม่อยู่ใน S1 มีเพียงสถานะเดียวคือ q6 ซึ่งไปถึงสถานะ q3 ได้ จะได้ S2 = {q0, q1, q2, q3, q6} เนื่องจาก S1 ≠ S2 จึงทำต่อไป
สร้างเซต S3 มีสถานะใหม่ที่ไปถึงสถานะใดสถานะหนึ่งใน S2 ได้หรือไม่ ไม่มี จากสถานะ q4 และ q5 ไปถึงสถานะใดใน S2 ไม่ได้ และสถานะอื่น ๆ ก็อยู่ใน S2 แล้ว ดังนั้น S3 = {q0, q1, q2, q3, q6} เนื่องจาก S2 = S3 ขั้นตอนวิธีจึงสิ้นสุด และเซต S2 คือเซตของสถานะที่ไม่ใช่สถานะที่ไม่จำเป็น ส่วนเซต {q4, q5} คือเซตของสถานะที่ไม่จำเป็น
ในทางรูปนัย ออโตมาตาใหม่ที่สมมูลกันและไม่มีสถานะที่ไม่จำเป็นสร้างได้ดังนี้ ให้ออโตมาตา A = ⟨Q, Σ, δ, q0, F⟩ สร้างออโตมาตาที่สมมูลกัน A′ = ⟨Q′, Σ, δ′, q0, F⟩ ซึ่งไม่มีสถานะที่ไม่จำเป็น
- ∀q ∈ Q′, a ∈ Σ: δ′(q, a) = δ(q, a) ถ้า δ(q, a) ∈ Q′ มิฉะนั้น δ′(q, a) ไม่นิยาม
แหล่งอ้างอิง
สารบัญ: สถานะที่ไปไม่ถึง, สถานะที่ไม่จำเป็น, การลดจำนวนสถานะของออโตมาตา