✖

การลดจำนวนสถานะของออโตมาตา

การลดจำนวนสถานะของออโตมาตา (minimization) คือการหาออโตมาตาที่สมมูลกันซึ่งมีจำนวนสถานะน้อยที่สุดเท่าที่เป็นไปได้ แม้ออโตมาตาที่ไม่มีสถานะที่ไม่จำเป็นเลยก็อาจทำให้ง่ายลงได้อีก

ตัวอย่าง

พิจารณาออโตมาตานี้:

ออโตมาตานี้ยอมรับเฉพาะสตริง 01 และ 11 จะเห็นได้ชัดว่ามีออโตมาตาที่ง่ายกว่าซึ่งมีสามสถานะและยอมรับภาษาเดียวกัน สถานะ q1 และ q2 รวมเป็นสถานะใหม่สถานะเดียว {q1, q2} ได้ การเปลี่ยนสถานะที่เคยเข้าสู่สถานะ q1 หรือ q2 จะเข้าสู่สถานะใหม่แทน และการเปลี่ยนสถานะที่ออกจาก q1 และ q2 ก็เช่นเดียวกัน จะได้ออโตมาตานี้:

เห็นได้ชัดว่าออโตมาตานี้ยอมรับภาษาเดียวกับออโตมาตาก่อนหน้า และมีสถานะน้อยกว่า

สถานะที่สมมูลกัน

ให้ออโตมาตา A = ⟨Q, Σ, δ, q0, F⟩ นิยามภาษาของสถานะ q ∈ Q เขียนแทนด้วย L(q) เป็น

L(q)=L(⟨Q,Σ,δ,q,F⟩)

นั่นคือ เปลี่ยนสถานะเริ่มต้นของออโตมาตา A จาก q0 เป็น q แล้วหาภาษาที่ออโตมาตานี้ยอมรับ กล่าวอีกอย่างคือ ภาษา L(q) ประกอบด้วยสตริง w ทั้งหมดซึ่งในออโตมาตา A สตริง w พาจากสถานะ q ไปถึงสถานะสิ้นสุดของออโตมาตาได้ กลับไปที่ออโตมาตาก่อนหน้า จะได้ L(q1) = {1}

สถานะสองสถานะที่ต่างกัน q1 และ q2 สมมูลกัน ถ้า

L(q1)=L(q2)

หมายความว่าอย่างไร ถ้าสถานะ q1, q2 สมมูลกัน เมื่อให้แต่ละสถานะเป็นสถานะเริ่มต้นของออโตมาตา จะก่อกำเนิดภาษาเดียวกัน กล่าวอีกอย่างคือ ถ้าออโตมาตาอยู่ในรูปแบบ ⟨q1, w⟩ และ ⟨q2, w⟩ ออโตมาตาต้องยอมรับในทั้งสองกรณี หรือปฏิเสธในทั้งสองกรณี

กลับไปที่ออโตมาตาก่อนหน้า สถานะ q1 และ q2 สมมูลกัน เพราะถ้าอยู่ที่สถานะ q1 จะยอมรับสตริงขาเข้าได้ก็ต่อเมื่อส่วนของสตริงที่ยังไม่ได้อ่านเท่ากับ 1 และเป็นเช่นเดียวกันถ้าอยู่ที่สถานะ q2

ดังนั้นการลดจำนวนสถานะของออโตมาตาคือการหาสถานะที่สมมูลกัน แล้วกำจัดออกโดยรวมเป็นสถานะใหม่สถานะเดียว เหมือนที่ทำในตัวอย่างข้างต้น

วิธีหาสถานะที่สมมูลกัน

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

เริ่มจากสร้างเซตของสถานะสองเซต

S1=F={q3,q6}S2=Q∖F={q0,q1,q2,q4,q5}

ต่อไปสร้างตารางการเปลี่ยนสถานะ โดยเก็บข้อมูลเกี่ยวกับกลุ่ม S1 และ S2 ไว้ด้วย:

กลุ่มสถานะ01S1q3q5q4q6——S2q0q1q2q1—q3q2—q3q4q6—q5q6—

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

กลุ่มสถานะ01S1q3S2S2q6——S2q0S2S2q1—S1q2—S1q4S1—q5S1—

ต่อไปแบ่งทั้งสองกลุ่มย่อยลงอีก สถานะที่สำหรับทุกสัญลักษณ์ไปยังกลุ่มเดียวกันจะอยู่ในกลุ่มเดียวกัน เช่น สถานะ q3 และ q6 จะไม่อยู่ในกลุ่มเดียวกัน เพราะสำหรับ 0 ทั้งสองไม่ได้ไปยังกลุ่มเดียวกัน และสำหรับ 1 ก็เช่นกัน ในทางกลับกัน สถานะ q1 และ q2 จะอยู่ในกลุ่มเดียวกัน เพราะทั้งสองสถานะไม่มีการเปลี่ยนสถานะสำหรับ 0 และสำหรับ 1 ทั้งสองไปที่กลุ่ม S1 จึงได้กลุ่มใหม่ดังนี้:

กลุ่มสถานะ01q3S2S2q6——q0S2S2q1—S1q2—S1q4S1—q5S1—

ในแต่ละกลุ่มมีการเปลี่ยนสถานะเหมือนกัน ตั้งชื่อกลุ่มที่เกิดขึ้นใหม่ แล้วหาอีกครั้งว่าสถานะต่าง ๆ ไปยังกลุ่มใหม่กลุ่มใด:

กลุ่มสถานะ01S1q3S5S5S2q6——S3q0S4S4S4q1—S1q2—S1S5q4S2—q5S2—

ถึงตอนนี้จะแบ่งกลุ่มต่อไปอีก แต่จะเห็นว่าแบ่งต่อไม่ได้แล้ว เพราะจะได้กลุ่มเดิม สถานะ q1 และ q2 มีการเปลี่ยนสถานะไปยังกลุ่มเดียวกันก็จริง แต่ทั้งสองอยู่ในกลุ่มเดียวกันอยู่แล้ว และไม่มีสถานะอื่นในกลุ่ม S4 อีก ขั้นตอนวิธีการหาสถานะที่สมมูลกันจึงสิ้นสุด จากแต่ละกลุ่มเพียงเลือกสถานะไว้หนึ่งสถานะ ลบสถานะอื่นออก และการเปลี่ยนสถานะทั้งหมดที่เคยเข้าสู่สถานะที่ลบออกจะเข้าสู่สถานะที่เลือกไว้แทน

ดังนั้นอาจเลือกให้ออโตมาตาใหม่มีสถานะ q3, q6, q0, q1, q4 และกำจัดสถานะ q2 และ q5 ออกได้ การเปลี่ยนสถานะทั้งหมดที่เคยเข้าสู่ q2 จะเข้าสู่ q1 และการเปลี่ยนสถานะทั้งหมดที่เคยเข้าสู่ q5 จะเข้าสู่ q4:

ขั้นตอนการลดจำนวนสถานะของออโตมาตา

  1. กำจัดสถานะที่ไปไม่ถึง
  2. กำจัดสถานะที่ไม่จำเป็น
  3. กำจัดสถานะที่สมมูลกัน

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

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