นิพจน์ปรกติ
นิพจน์ปรกติ (regular expression) คือสตริงข้อความที่ใช้อธิบายเซตของสตริงเซตหนึ่ง อาจมองนิพจน์ปรกติเป็นวิธีง่าย ๆ ในการอธิบายออโตมาตาจำกัดก็ได้
นิพจน์ปรกติคืออะไร
ในเลขคณิตใช้สัญลักษณ์อย่าง · และ + สร้างนิพจน์ เช่น (2 + 3) · 4 เมื่อหาค่าของนิพจน์นี้จะได้จำนวน นิพจน์ปรกติคือลำดับของอักขระและสัญลักษณ์พิเศษบางตัว เช่น a(x ∪ y) ซึ่งเมื่อหาค่าแล้วจะได้ภาษา (รูปนัย) ผลลัพธ์ของนิพจน์ (2 + 3) · 4 คือจำนวน 20 ส่วนผลลัพธ์ของนิพจน์ปรกติ a(x ∪ y) คือเซตของสตริงสองสตริง “ax” และ “ay”
จะหาค่าของนิพจน์ปรกติ a(x ∪ y) ข้างต้นได้อย่างไร ที่จริงแล้วตัวอักษรแต่ละตัวเป็นตัวย่อของเซตที่มีสมาชิกตัวเดียว (singleton) คือตัวอักษรนั้น และการคูณที่ไม่ได้เขียนไว้คือการต่อสตริง นิพจน์ปรกตินี้เขียน “แบบเต็ม” ได้ดังนี้:
จากนั้นหาค่าดังนี้ ยูเนียน {x} ∪ {y} ให้ภาษา {x,y} การต่อภาษา {a} กับ {x,y} ให้ภาษา {ax, ay}
นิพจน์ปรกติใช้บ่อยมากในการเขียนโปรแกรม และภาษาโปรแกรมส่วนใหญ่มีนิพจน์ปรกติในรูปแบบใดรูปแบบหนึ่ง นิพจน์ปรกติจึงใช้ เช่น ตรวจสอบว่าข้อความที่ผู้ใช้ป้อนเป็นไปตามเกณฑ์ที่กำหนดหรือไม่ (เช่น เป็นที่อยู่อีเมลที่ถูกต้อง หรือวันที่ที่ถูกต้อง) และใช้แทนที่ข้อความ (เช่น อาจต้องการแทนที่ URL ทุกตัวในข้อความด้วยลิงก์ที่คลิกได้)
นิพจน์ปรกติที่ใช้งานจริงส่วนใหญ่มีความสามารถมากกว่านิพจน์ปรกติที่อธิบายไว้ในที่นี้ และใช้ไวยากรณ์ที่ต่างไปเล็กน้อย แต่ที่สำคัญคือซับซ้อนกว่า
นิยามของนิพจน์ปรกติ
จะนิยามนิพจน์ปรกติบนอักษร Σ ใดอักษรหนึ่ง นิพจน์ปรกติคือ:
- a โดยที่ a ∈ Σ นั่นคือ อักขระหนึ่งตัวของอักษรเป็นนิพจน์ปรกติ
- ϵ: สตริงว่าง ในการเขียนโปรแกรมเขียนเป็นอัญประกาศเปล่า “” ก็ได้
- ∅: นิพจน์ปรกติต้องอธิบายภาษาว่างได้ด้วย ดังนั้นภาษาว่างเป็นนิพจน์ปรกติ
- (R1 ∪ R2) โดยที่ R1, R2 เป็นนิพจน์ปรกติ
- (R1 ∘ R2) โดยที่ R1, R2 เป็นนิพจน์ปรกติ
- (R∗) โดยที่ R เป็นนิพจน์ปรกติ
แทนที่จะใช้สัญลักษณ์ ∪ ในข้อ 4 อาจใช้สัญลักษณ์ขีดตั้ง | ก็ได้ และแทนที่จะใช้สัญลักษณ์ ∘ ก็ไม่ต้องเขียนอะไรเลยก็ได้ เช่นเดียวกับที่ส่วนใหญ่ไม่ได้เขียนสัญลักษณ์การคูณซึ่งเป็นจุดกลาง · ก็มักไม่เขียนสัญลักษณ์การต่อ ∘ เช่นกัน ดังนั้นนิพจน์ปรกติต่อไปนี้เหมือนกัน: a ∘ (b ∪ c) และ a(b|c)
ตัวดำเนินการแต่ละตัวหมายความว่าอย่างไร
- ∪ หรือ | แทนยูเนียนของภาษา
- ∘ แทนการต่อภาษา
- ∗ แทนส่วนปิดคลุมของภาษา
ตัวอย่าง:
- a แทนภาษาอย่างง่าย {a}
- a|b แทนภาษาที่ประกอบด้วยสตริงสองสตริง {a, b}
- a ∘ b แทนภาษา {ab}
- a(b|c)d แทนภาษา {abd, acd}
- a(b∗) แทนภาษาของสตริงทั้งหมดที่ขึ้นต้นด้วยตัวอักษร “a” แล้วตามด้วยตัวอักษร “b” กี่ตัวก็ได้
- (ab)∗ แทนภาษาของสตริงทั้งหมด {ϵ, ab, abab, ababab, …}
- 0∗10∗ แทนภาษาของสตริงฐานสองทั้งหมดที่มีเลข 1 เพียงตัวเดียว (สังเกตว่าถ้าจะให้ละเอียดกว่านี้ ควรเขียนนิพจน์นี้เป็น (0∗)1(0∗) แต่เมื่ออ่านเข้าใจได้แม้ไม่มีวงเล็บ ก็ละวงเล็บได้)
- Σ∗1Σ∗ แทนภาษาของสตริงทั้งหมดที่มีเลข 1 อย่างน้อยหนึ่งตัว
- (1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)∗ แทนภาษาของจำนวนนับทั้งหมด
ต่อไปจะแสดงว่านิพจน์ปรกติสมมูลกับออโตมาตาจำกัด กล่าวคือ สำหรับทุกนิพจน์ปรกติซึ่งเมื่อหาค่าแล้วได้ภาษา R จะมีออโตมาตาจำกัด A ที่ทำให้ L(A) = R และในทางกลับกันก็เป็นจริงด้วย
แหล่งอ้างอิง
สารบัญ: นิพจน์ปรกติ, การแปลงนิพจน์ปรกติเป็นออโตมาตา, ออโตมาตาจำกัดแบบนอนดีเทอร์มินิสติกทั่วไป, การแปลงออโตมาตาเป็นนิพจน์ปรกติ