✖

การแปลงออโตมาตาเป็นนิพจน์ปรกติ

บทความนี้จะแสดงวิธีแปลงออโตมาตาจำกัดใด ๆ เป็นนิพจน์ปรกติ

คำอธิบายขั้นตอนวิธี

สิ่งที่ป้อนเข้าคือ NFA A ตัวหนึ่ง อย่างแรกแปลงออโตมาตานี้เป็น GNFA ในขั้นที่สอง แต่ละครั้งกำจัดสถานะออกหนึ่งสถานะ แก้ฟังก์ชันการเปลี่ยนสถานะให้ถูกต้อง และทำซ้ำจนเหลือเพียงสองสถานะ คือสถานะเริ่มต้นและสถานะสิ้นสุด ระหว่างสองสถานะนี้จะมีเส้นเชื่อมที่กำกับด้วยนิพจน์ปรกติ ซึ่งเป็นผลลัพธ์ของขั้นตอนวิธีทั้งหมด หัวใจของขั้นตอนนี้จึงอยู่ที่การกำจัดสถานะ (state elimination) แล้วแก้ออโตมาตาให้ได้ออโตมาตาที่สมมูลกัน

การกำจัดสถานะหนึ่งสถานะ

วิธีกำจัดสถานะหนึ่งสถานะแสดงได้ด้วยตัวอย่างง่าย ๆ สมมติว่าส่วนหนึ่งของออโตมาตามีลักษณะดังนี้:

โดยที่ Ri เป็นนิพจน์ปรกติ ถ้ากำจัดสถานะ qr ออกไป ออโตมาตาจะมีลักษณะอย่างไร อาจนึกภาพว่าอยู่ที่สถานะ qi แล้วถามว่าในส่วนนี้สร้างสตริงใดได้บ้าง ถ้าไปจากสถานะ qi ตรงไปที่สถานะ qj จะได้สตริงทั้งหมดที่ตรงกับนิพจน์ปรกติ R4

แต่ถ้าไปที่สถานะ qr จะสร้างสตริงในรูป R1 ได้ ที่สถานะ qr ยังวนซ้ำได้ด้วยนิพจน์ปรกติ R2 จึงสร้างสตริงในรูป R1∘(R2∗) ได้ และเนื่องจากจากสถานะ qr ยังไปที่สถานะ qj ได้อีก จึงเติมนิพจน์ปรกติ R3 เข้าไป รวมแล้วเส้นทางนี้ให้สตริงในรูป R1∘(R2∗)∘R3

ตอนนี้ทราบแล้วว่าส่วนนี้ของออโตมาตาให้สตริงในรูป R4 หรือในรูป R1∘(R2∗)∘R3 ซึ่งแน่นอนว่าเขียนเป็นนิพจน์ปรกติได้เป็น (R4)|(R1∘(R2∗)∘R3)

ตอนนี้กำจัดสถานะ qr ออกได้ง่าย ๆ เหลือเพียงสองสถานะ qi และ qj แล้วเขียนนิพจน์ปรกติที่เพิ่งคำนวณได้แทน R4:

ทำขั้นตอนนี้กับทุกเส้นเชื่อมจากทุกสถานะ qi ไปยังสถานะ qj รวมทั้งวงวน นั่นคือรวมทั้งกรณีที่ qi = qj

หลังกำจัดสถานะหนึ่งสถานะ จะได้ออโตมาตาที่สมมูลกัน คือออโตมาตาที่จำแนกภาษาเดียวกัน

ขั้นตอนวิธีทั้งหมด

สิ่งที่ป้อนเข้าคือ NFA A = ⟨Q, Σ, δ, q0, F⟩

  1. แปลง NFA A เป็น GNFA Z = ⟨Q′, Σ, δ′, q0′, qf′⟩ ต่อไปให้ k แทนจำนวนสถานะใน Z
  2. ถ้า k = 2 ขั้นตอนวิธีสิ้นสุด และนิพจน์ปรกติที่ได้อยู่บนเส้นเชื่อมระหว่างสถานะเริ่มต้นกับสถานะสิ้นสุด
  3. ถ้า k>2 เลือกสถานะ qr ใดก็ได้ที่ไม่ใช่สถานะเริ่มต้นและไม่ใช่สถานะสิ้นสุด นั่นคือ qr ≠ q0′ และ qr ≠ qf′ แล้วสร้าง GNFA ใหม่ Z′ = ⟨Q′′, Σ, δ′′,q0′,qf′⟩ โดยที่: Q′′=Q′∖{qr} และสำหรับทุก qi ∈ Q′′ ∖ {qf′} และทุก qj ∈ Q′′ ∖ {q0′} ให้ δ′′(qi,qj)=(R4)|(R1(R2∗)R3) โดยที่ 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)∗

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

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

สารบัญ: นิพจน์ปรกติ, การแปลงนิพจน์ปรกติเป็นออโตมาตา, ออโตมาตาจำกัดแบบนอนดีเทอร์มินิสติกทั่วไป, การแปลงออโตมาตาเป็นนิพจน์ปรกติ