การแปลงนิพจน์ปรกติเป็นออโตมาตา
บทความนี้จะแสดงวิธีแปลงนิพจน์ปรกติใด ๆ เป็นออโตมาตาจำกัดแบบนอนดีเทอร์มินิสติก
ตัวอย่าง
ก่อนอธิบายขั้นตอนวิธี จะใช้ตัวอย่างแสดงให้เห็นว่าต้องการทำอะไร ให้นิพจน์ปรกติคือ a(b|c)x∗ ภาษาที่นิพจน์ปรกตินี้ก่อกำเนิดอธิบายเป็นถ้อยคำได้ว่า เป็นสตริงที่ขึ้นต้นด้วยตัวอักษร “a” ตามด้วยตัวอักษร “b” หรือ “c” แล้วตามด้วยตัวอักษร “x” กี่ตัวก็ได้ จะสร้างออโตมาตาที่ยอมรับภาษานี้ได้หรือไม่ ได้ ดังนี้:
เห็นได้ชัดว่าออโตมาตานี้ยอมรับภาษาเดียวกัน จึงเกิดคำถามว่าสำหรับทุกนิพจน์ปรกติ จะมีออโตมาตาที่ยอมรับภาษานั้นหรือไม่ คำตอบคือ มี
ขั้นตอนวิธีการแปลงนิพจน์ปรกติเป็นออโตมาตา
สมมติว่าสิ่งที่ป้อนเข้าคือนิพจน์ปรกติ R จากหัวข้อนิพจน์ปรกติทราบแล้วว่านิพจน์ปรกติมีรูปแบบที่ต่างกันทั้งหมดหกแบบ จึงแยกพิจารณาหกกรณี:
-
R = a สำหรับสัญลักษณ์ a ∈ Σ บางตัว นั่นคือนิพจน์ปรกติเป็นเพียงสัญลักษณ์หนึ่งตัวจากอักษร Σ ที่ใช้อยู่ ออโตมาตาที่ยอมรับสัญลักษณ์ a หนึ่งตัวมีลักษณะดังนี้:
-
R = ϵ สตริงว่าง ออโตมาตาที่ยอมรับสตริงว่างมีลักษณะดังนี้:
-
R = ∅ นิพจน์ปรกติที่ก่อกำเนิดภาษาว่าง ออโตมาตาที่จำแนกภาษาเช่นนี้ได้คือ:
-
R = R1 ∪ R2 โดยที่ R1, R2 เป็นนิพจน์ปรกติ ทราบแล้วว่ายูเนียนของภาษาปรกติเป็นภาษาปรกติ และสร้างออโตมาตาที่ยอมรับภาษาเช่นนี้ได้ กล่าวอีกอย่างคือ สมมติว่ามีออโตมาตาที่จำแนกภาษาซึ่งนิพจน์ R1 และ R2 ก่อกำเนิด แล้วใช้ออโตมาตาเหล่านี้สร้างออโตมาตาที่ยอมรับภาษาซึ่งนิพจน์ R1 ∪ R2 ก่อกำเนิด ตัวอย่างเช่น ถ้า R1 = a และ R2 = ϵ ตามขั้นตอนจะได้ออโตมาตานี้:
-
R = R1 ∘ R2 โดยที่ R1, R2 เป็นนิพจน์ปรกติ เป็นกรณีเดียวกับข้อก่อน การต่อภาษาปรกติได้ภาษาปรกติ จึงสร้างออโตมาตาที่ยอมรับภาษาเช่นนี้ได้ ดังนั้นถ้า R1 = a และ R2 = b การต่อจะมีลักษณะดังนี้:
-
โดยที่ R1 เป็นนิพจน์ปรกติ ทราบแล้วเช่นกันว่าส่วนปิดคลุมของภาษาปรกติเป็นภาษาปรกติ ดังนั้นถ้า R = a∗ ออโตมาตาจะมีลักษณะดังนี้:
เมื่อใช้ข้อเหล่านี้ทีละขั้น จะแปลงนิพจน์ปรกติทั้งนิพจน์เป็นออโตมาตาจำกัดได้
ตัวอย่างฉบับสมบูรณ์
ลองแปลงนิพจน์ปรกติ (a|bc)∗ จะได้ออโตมาตาต่อไปนี้ตามลำดับ:
ออโตมาตาที่ได้สุดท้ายนี้ยอมรับภาษาที่นิพจน์ปรกติ (a|bc)∗ ก่อกำเนิด แน่นอนว่าออโตมาตานี้ซับซ้อนมาก และมีออโตมาตาที่ง่ายกว่ามากซึ่งยอมรับภาษาเดียวกันแน่นอน อาจใช้ขั้นตอนวิธีแปลง NFA เป็น DFA แล้วจึงลดจำนวนสถานะของออโตมาตา
แหล่งอ้างอิง
สารบัญ: นิพจน์ปรกติ, การแปลงนิพจน์ปรกติเป็นออโตมาตา, ออโตมาตาจำกัดแบบนอนดีเทอร์มินิสติกทั่วไป, การแปลงออโตมาตาเป็นนิพจน์ปรกติ