การแปลงออโตมาตาเป็นนิพจน์ปรกติ
บทความนี้จะแสดงวิธีแปลงออโตมาตาจำกัดใด ๆ เป็นนิพจน์ปรกติ
คำอธิบายขั้นตอนวิธี
สิ่งที่ป้อนเข้าคือ NFA A ตัวหนึ่ง อย่างแรกแปลงออโตมาตานี้เป็น GNFA ในขั้นที่สอง แต่ละครั้งกำจัดสถานะออกหนึ่งสถานะ แก้ฟังก์ชันการเปลี่ยนสถานะให้ถูกต้อง และทำซ้ำจนเหลือเพียงสองสถานะ คือสถานะเริ่มต้นและสถานะสิ้นสุด ระหว่างสองสถานะนี้จะมีเส้นเชื่อมที่กำกับด้วยนิพจน์ปรกติ ซึ่งเป็นผลลัพธ์ของขั้นตอนวิธีทั้งหมด หัวใจของขั้นตอนนี้จึงอยู่ที่การกำจัดสถานะ (state elimination) แล้วแก้ออโตมาตาให้ได้ออโตมาตาที่สมมูลกัน
การกำจัดสถานะหนึ่งสถานะ
วิธีกำจัดสถานะหนึ่งสถานะแสดงได้ด้วยตัวอย่างง่าย ๆ สมมติว่าส่วนหนึ่งของออโตมาตามีลักษณะดังนี้:
โดยที่ Ri เป็นนิพจน์ปรกติ ถ้ากำจัดสถานะ qr ออกไป ออโตมาตาจะมีลักษณะอย่างไร อาจนึกภาพว่าอยู่ที่สถานะ qi แล้วถามว่าในส่วนนี้สร้างสตริงใดได้บ้าง ถ้าไปจากสถานะ qi ตรงไปที่สถานะ qj จะได้สตริงทั้งหมดที่ตรงกับนิพจน์ปรกติ R4
แต่ถ้าไปที่สถานะ qr จะสร้างสตริงในรูป R1 ได้ ที่สถานะ qr ยังวนซ้ำได้ด้วยนิพจน์ปรกติ R2 จึงสร้างสตริงในรูป
ตอนนี้ทราบแล้วว่าส่วนนี้ของออโตมาตาให้สตริงในรูป R4 หรือในรูป
ตอนนี้กำจัดสถานะ qr ออกได้ง่าย ๆ เหลือเพียงสองสถานะ qi และ qj แล้วเขียนนิพจน์ปรกติที่เพิ่งคำนวณได้แทน R4:
ทำขั้นตอนนี้กับทุกเส้นเชื่อมจากทุกสถานะ qi ไปยังสถานะ qj รวมทั้งวงวน นั่นคือรวมทั้งกรณีที่ qi = qj
หลังกำจัดสถานะหนึ่งสถานะ จะได้ออโตมาตาที่สมมูลกัน คือออโตมาตาที่จำแนกภาษาเดียวกัน
ขั้นตอนวิธีทั้งหมด
สิ่งที่ป้อนเข้าคือ NFA A = ⟨Q, Σ, δ, q0, F⟩
- แปลง NFA A เป็น GNFA Z = ⟨Q′, Σ, δ′, q0′, qf′⟩ ต่อไปให้ k แทนจำนวนสถานะใน Z
- ถ้า k = 2 ขั้นตอนวิธีสิ้นสุด และนิพจน์ปรกติที่ได้อยู่บนเส้นเชื่อมระหว่างสถานะเริ่มต้นกับสถานะสิ้นสุด
- ถ้า k>2 เลือกสถานะ qr ใดก็ได้ที่ไม่ใช่สถานะเริ่มต้นและไม่ใช่สถานะสิ้นสุด นั่นคือ qr ≠ q0′ และ qr ≠ qf′ แล้วสร้าง GNFA ใหม่ Z′ = ⟨Q′′, Σ, δ′′,q0′,qf′⟩ โดยที่:
และสำหรับทุก qi ∈ Q′′ ∖ {qf′} และทุก qj ∈ Q′′ ∖ {q0′} ให้ โดยที่ R1 = δ′(qi,qr) R2 = δ′(qr,qr) R3 = δ′(qr, qj) และ R4 = δ′(qi, qj) แล้วกลับไปทำขั้นที่ 2
ตัวอย่าง
ให้ออโตมาตาจำกัดที่ป้อนเข้าเป็นดังนี้:
อย่างแรกแปลงเป็น GNFA (การเปลี่ยนสถานะ ∅ ที่ไม่จำเป็นจะไม่แสดงในรูป):
ต่อไปใช้ขั้นตอนวิธีส่วนที่สองและกำจัดปมออกหนึ่งปม เริ่มจากปม q2 กำจัดปม q2 แล้วเพิ่มการเปลี่ยนสถานะจากสถานะ q1 ไปยังสถานะ qf กำกับการเปลี่ยนสถานะนี้ด้วย b(a|b)∗ เพราะจากปม q1 ไปถึงสถานะ q2 ด้วยสตริงในรูป b จากนั้นวนซ้ำด้วย a|b ได้ ซึ่งให้ (a|b)∗ และสุดท้ายใช้กฎเอปไซลอนไปที่ qf โดยที่ b(a|b)∗ϵ = b(a|b)∗ จะได้ออโตมาตา:
เหลือเพียงกำจัดสถานะสุดท้าย q1 เพิ่มเส้นเชื่อมจากสถานะ qs ไปยังสถานะ qf จะกำกับเส้นเชื่อมนี้อย่างไร ไปถึงสถานะ q1 ด้วยกฎเอปไซลอน ซึ่งตัดทิ้งได้เลย จากนั้นวนซ้ำด้วย a ได้ จึงได้นิพจน์ปรกติ a∗ และสุดท้ายใช้เส้นเชื่อมไปที่ qf จึงต่อนิพจน์ด้วย b(a|b)∗ เส้นเชื่อมจึงกำกับด้วยนิพจน์ปรกติ a∗ b(a|b)∗
ออโตมาตาเหลือเพียงสองสถานะแล้ว ขั้นตอนวิธีจึงสิ้นสุด นิพจน์ปรกติที่ได้อยู่บนเส้นเชื่อม
แหล่งอ้างอิง
- ตัวอย่างและคำอธิบายขั้นตอนวิธีมาจาก M. Sipser: Introduction to the Theory of Computation
สารบัญ: นิพจน์ปรกติ, การแปลงนิพจน์ปรกติเป็นออโตมาตา, ออโตมาตาจำกัดแบบนอนดีเทอร์มินิสติกทั่วไป, การแปลงออโตมาตาเป็นนิพจน์ปรกติ