การลดจำนวนสถานะของออโตมาตา
การลดจำนวนสถานะของออโตมาตา (minimization) คือการหาออโตมาตาที่สมมูลกันซึ่งมีจำนวนสถานะน้อยที่สุดเท่าที่เป็นไปได้ แม้ออโตมาตาที่ไม่มีสถานะที่ไม่จำเป็นเลยก็อาจทำให้ง่ายลงได้อีก
ตัวอย่าง
พิจารณาออโตมาตานี้:
ออโตมาตานี้ยอมรับเฉพาะสตริง 01 และ 11 จะเห็นได้ชัดว่ามีออโตมาตาที่ง่ายกว่าซึ่งมีสามสถานะและยอมรับภาษาเดียวกัน สถานะ q1 และ q2 รวมเป็นสถานะใหม่สถานะเดียว {q1, q2} ได้ การเปลี่ยนสถานะที่เคยเข้าสู่สถานะ q1 หรือ q2 จะเข้าสู่สถานะใหม่แทน และการเปลี่ยนสถานะที่ออกจาก q1 และ q2 ก็เช่นเดียวกัน จะได้ออโตมาตานี้:
เห็นได้ชัดว่าออโตมาตานี้ยอมรับภาษาเดียวกับออโตมาตาก่อนหน้า และมีสถานะน้อยกว่า
สถานะที่สมมูลกัน
ให้ออโตมาตา A = ⟨Q, Σ, δ, q0, F⟩ นิยามภาษาของสถานะ q ∈ Q เขียนแทนด้วย L(q) เป็น
นั่นคือ เปลี่ยนสถานะเริ่มต้นของออโตมาตา A จาก q0 เป็น q แล้วหาภาษาที่ออโตมาตานี้ยอมรับ กล่าวอีกอย่างคือ ภาษา L(q) ประกอบด้วยสตริง w ทั้งหมดซึ่งในออโตมาตา A สตริง w พาจากสถานะ q ไปถึงสถานะสิ้นสุดของออโตมาตาได้ กลับไปที่ออโตมาตาก่อนหน้า จะได้ L(q1) = {1}
สถานะสองสถานะที่ต่างกัน q1 และ q2 สมมูลกัน ถ้า
หมายความว่าอย่างไร ถ้าสถานะ q1, q2 สมมูลกัน เมื่อให้แต่ละสถานะเป็นสถานะเริ่มต้นของออโตมาตา จะก่อกำเนิดภาษาเดียวกัน กล่าวอีกอย่างคือ ถ้าออโตมาตาอยู่ในรูปแบบ ⟨q1, w⟩ และ ⟨q2, w⟩ ออโตมาตาต้องยอมรับในทั้งสองกรณี หรือปฏิเสธในทั้งสองกรณี
กลับไปที่ออโตมาตาก่อนหน้า สถานะ q1 และ q2 สมมูลกัน เพราะถ้าอยู่ที่สถานะ q1 จะยอมรับสตริงขาเข้าได้ก็ต่อเมื่อส่วนของสตริงที่ยังไม่ได้อ่านเท่ากับ 1 และเป็นเช่นเดียวกันถ้าอยู่ที่สถานะ q2
ดังนั้นการลดจำนวนสถานะของออโตมาตาคือการหาสถานะที่สมมูลกัน แล้วกำจัดออกโดยรวมเป็นสถานะใหม่สถานะเดียว เหมือนที่ทำในตัวอย่างข้างต้น
วิธีหาสถานะที่สมมูลกัน
สถานะแบบใดที่ไม่สมมูลกันแน่นอน ถ้าเลือกสถานะสิ้นสุดหนึ่งสถานะและสถานะที่ไม่ใช่สถานะสิ้นสุดหนึ่งสถานะ ทั้งสองไม่สมมูลกันแน่นอน เพราะภาษาของสถานะสิ้นสุดต่างจากภาษาของสถานะที่ไม่ใช่สถานะสิ้นสุด สถานะสิ้นสุดยอมรับสตริง ε แน่นอน แต่สถานะที่ไม่ใช่สถานะสิ้นสุดไม่ยอมรับ จะแสดงขั้นตอนด้วยตัวอย่างเลย ให้ออโตมาตาเป็นดังนี้:
เริ่มจากสร้างเซตของสถานะสองเซต
ต่อไปสร้างตารางการเปลี่ยนสถานะ โดยเก็บข้อมูลเกี่ยวกับกลุ่ม S1 และ S2 ไว้ด้วย:
ตอนนี้ปรับตาราง แทนที่จะเขียนในตารางว่าสำหรับสัญลักษณ์ที่กำหนดไปที่สถานะใด จะเขียนเพียงกลุ่มที่ไป เช่น จากสถานะ q3 สำหรับ 0 จะไปที่สถานะ q5 ซึ่งอยู่ในกลุ่ม S2 จึงเขียน S2 ลงในตารางแทน q5:
ต่อไปแบ่งทั้งสองกลุ่มย่อยลงอีก สถานะที่สำหรับทุกสัญลักษณ์ไปยังกลุ่มเดียวกันจะอยู่ในกลุ่มเดียวกัน เช่น สถานะ q3 และ q6 จะไม่อยู่ในกลุ่มเดียวกัน เพราะสำหรับ 0 ทั้งสองไม่ได้ไปยังกลุ่มเดียวกัน และสำหรับ 1 ก็เช่นกัน ในทางกลับกัน สถานะ q1 และ q2 จะอยู่ในกลุ่มเดียวกัน เพราะทั้งสองสถานะไม่มีการเปลี่ยนสถานะสำหรับ 0 และสำหรับ 1 ทั้งสองไปที่กลุ่ม S1 จึงได้กลุ่มใหม่ดังนี้:
ในแต่ละกลุ่มมีการเปลี่ยนสถานะเหมือนกัน ตั้งชื่อกลุ่มที่เกิดขึ้นใหม่ แล้วหาอีกครั้งว่าสถานะต่าง ๆ ไปยังกลุ่มใหม่กลุ่มใด:
ถึงตอนนี้จะแบ่งกลุ่มต่อไปอีก แต่จะเห็นว่าแบ่งต่อไม่ได้แล้ว เพราะจะได้กลุ่มเดิม สถานะ q1 และ q2 มีการเปลี่ยนสถานะไปยังกลุ่มเดียวกันก็จริง แต่ทั้งสองอยู่ในกลุ่มเดียวกันอยู่แล้ว และไม่มีสถานะอื่นในกลุ่ม S4 อีก ขั้นตอนวิธีการหาสถานะที่สมมูลกันจึงสิ้นสุด จากแต่ละกลุ่มเพียงเลือกสถานะไว้หนึ่งสถานะ ลบสถานะอื่นออก และการเปลี่ยนสถานะทั้งหมดที่เคยเข้าสู่สถานะที่ลบออกจะเข้าสู่สถานะที่เลือกไว้แทน
ดังนั้นอาจเลือกให้ออโตมาตาใหม่มีสถานะ q3, q6, q0, q1, q4 และกำจัดสถานะ q2 และ q5 ออกได้ การเปลี่ยนสถานะทั้งหมดที่เคยเข้าสู่ q2 จะเข้าสู่ q1 และการเปลี่ยนสถานะทั้งหมดที่เคยเข้าสู่ q5 จะเข้าสู่ q4:
ขั้นตอนการลดจำนวนสถานะของออโตมาตา
- กำจัดสถานะที่ไปไม่ถึง
- กำจัดสถานะที่ไม่จำเป็น
- กำจัดสถานะที่สมมูลกัน
แหล่งอ้างอิง
สารบัญ: สถานะที่ไปไม่ถึง, สถานะที่ไม่จำเป็น, การลดจำนวนสถานะของออโตมาตา