✖

สถานะที่ไปไม่ถึง

ออโตมาตาจำกัดอาจมีสถานะที่ไม่มีทางไปถึงได้ สถานะเช่นนี้เรียกว่าสถานะที่ไปไม่ถึง (unreachable state) โดยทั่วไปต้องการกำจัดสถานะเหล่านี้ออก เพราะทำให้ออโตมาตาซับซ้อนขึ้นโดยไม่จำเป็น

ตัวอย่างของสถานะที่ไปไม่ถึง

ให้ออโตมาตาเป็นดังนี้:

จะเห็นว่าไม่ว่าจะทำอย่างไร ก็ไปไม่ถึงสถานะ q3 เลย เพราะไม่มีการเปลี่ยนสถานะใดเข้าสู่สถานะนี้ จึงกล่าวว่าสถานะ q3 เป็นสถานะที่ไปไม่ถึง คำถามคือ ถ้ามีการเปลี่ยนสถานะจากสถานะอื่นเข้าสู่สถานะ q3 สถานะนี้จะไปถึงได้หรือไม่ ถ้าลากเส้นเชื่อมจากสถานะใดสถานะหนึ่งใน q0, q1, q2, q5 สถานะนี้จะไปถึงได้ แต่ถ้าเพิ่มปมใหม่แล้วลากการเปลี่ยนสถานะจากปมนั้น…

…แน่นอนว่าทั้งสถานะ q3 และ q4 จะเป็นสถานะที่ไปไม่ถึง

นิยามของสถานะที่ไปไม่ถึง

อย่างแรกจะนิยามสถานะที่ไปถึงได้ ให้ออโตมาตาจำกัด A = ⟨Q, Σ, δ, q0, F⟩ สถานะ q ∈ Q เป็นสถานะที่ไปถึงได้ ถ้ามีสตริง w ∈ Σ∗ ที่ทำให้

⟨q0,w⟩↦∗⟨q,ε⟩

สถานะ q ∈ Q เป็นสถานะที่ไปไม่ถึง ถ้าสถานะนั้นไม่ใช่สถานะที่ไปถึงได้

วิธีกำจัดสถานะที่ไปไม่ถึง

ถ้าออโตมาตามีสถานะที่ไปไม่ถึงอยู่แล้ว ควรกำจัดสถานะเหล่านั้นออก จึงสร้างออโตมาตาที่สมมูลกัน A′ = ⟨Q′, Σ, δ′, q0, F′⟩ ซึ่งไม่มีสถานะที่ไปไม่ถึง

จะสร้างเซตของสถานะที่ไปถึงได้ทีละขั้น เริ่มจากเซต S0 = {q0} เพราะสถานะเริ่มต้นไปถึงได้แน่นอน เซตถัดไปสร้างดังนี้:

Si={r|δ(q,a)=r สำหรับบาง q∈Si−1,a∈Σ}∪Si−1

กล่าวเป็นภาษาธรรมดาคือ เซต S0 กำหนดไว้แล้วเสมอ เซต S1 สร้างโดยนำทุกสถานะจากเซต S0 มาหาว่าการเปลี่ยนสถานะสำหรับทุกสัญลักษณ์จาก Σ พาไปที่สถานะใดบ้าง แล้วนำสถานะเหล่านี้มายูเนียนกับเซตของสถานะเดิม S0 หาเซต S2 และเซตถัด ๆ ไปด้วยวิธีเดียวกัน จะเห็นได้ชัดว่า Si − 1 ⊆ Si

จากนั้นจะได้เซตของสถานะที่ไปถึงได้ดังนี้:

⋃i=1∞Si

การยูเนียนเซต Si จำนวนมากมายไม่จำกัดอาจดูแปลก แต่ออโตมาตามีจำนวนสถานะจำกัด หมายความว่าถึงจุดหนึ่ง เซต Sj และ Sj + 1 รวมทั้งเซตถัด ๆ ไปทั้งหมดจะเท่ากัน ดังนั้นแม้จะยูเนียนเซตจำนวนมากมายไม่จำกัด ก็ได้เซตของสถานะที่จำกัดได้

กลับไปที่ออโตมาตา

แล้วลองหาเซตของสถานะที่ไปถึงได้ เริ่มจากกำหนดค่าเริ่มต้น

S0={q0}

ต่อไปคำนวณเซต S1 ต้องหาการเปลี่ยนสถานะทั้งหมดจากสถานะ q0 แล้วเพิ่มสถานะปลายทางลงในเซต S0 เนื่องจาก q0 → a q1 และ q0 → bq2 เซต S1 จึงมีสถานะ q1 และ q2 เพิ่มเข้ามา:

S1={q0,q1,q2}

ต่อไปสร้างเซต S2 ดูว่าจากสถานะ q0, q1, q2 ไปที่ใดได้บ้าง สถานะใหม่มีเพียง q5 ซึ่งไปถึงได้จากสถานะ q1:

S2={q0,q1,q2,q5}

ต่อไปสร้างเซต S3 จากสถานะ q0, q1, q2, q5 ไปถึงสถานะใหม่ได้หรือไม่ ไม่ได้ ดังนั้นเซต S3 จะมีสมาชิกเหมือนกับ S2:

S3={q0,q1,q2,q5}

เนื่องจาก S2 = S3 จึงได้ S3 = S4 = S5 = … ด้วย ถ้ายูเนียน Si ทั้งหมด จะได้เซต S2 เพราะไม่มีสมาชิกใหม่เพิ่มเข้ามาในเซตถัด ๆ ไปอีกเลย

ดังนั้นเซตของสถานะที่ไปถึงได้ของออโตมาตาคือ {q0, q1, q2, q5} สถานะที่ไปไม่ถึงหาได้จากผลต่างของเซต:

Q∖⋃i=1∞Si

เซตของสถานะที่ไปไม่ถึงของออโตมาตานี้คือ {q3, q4} กำจัดสถานะที่ไปไม่ถึงทั้งหมดและการเปลี่ยนสถานะทั้งหมดที่เกี่ยวข้องกับสถานะที่ไปไม่ถึงออกจากออโตมาตา A นั่นคือ ออโตมาตาที่สมมูลกันและไม่มีสถานะที่ไปไม่ถึง A′ = ⟨Q′, Σ, δ′, q0, F′⟩ ของออโตมาตา A = ⟨Q, Σ, δ, q0, F⟩ นิยามเป็น:

  • Q′=⋃i=1∞Si
  • ∀q ∈ Q′, a ∈ Σ:  δ′(q, a) = δ(q, a)
  • F′=F∩Q′=F∩⋃i=1∞Si

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

สารบัญ: สถานะที่ไปไม่ถึง, สถานะที่ไม่จำเป็น, การลดจำนวนสถานะของออโตมาตา