ออโตมาตาจำกัด
ออโตมาตาจำกัด (finite automaton หรือ finite state machine) คือแบบจำลองการคำนวณ (model of computation) ของคอมพิวเตอร์อย่างง่าย ซึ่งประกอบด้วยสถานะ (state) จำนวนหนึ่งและการเปลี่ยนสถานะ (transition) จำนวนหนึ่ง และสามารถยอมรับ (accept) หรือปฏิเสธ (reject) สตริงที่ป้อนเข้าไปได้
ตัวอย่าง
อธิบายออโตมาตาจำกัดอย่างไม่เป็นทางการได้ด้วยแผนภาพสถานะ (state diagram) ซึ่งแสดงออโตมาตาจำกัดนั้น:
ออโตมาตาประกอบด้วยสถานะ ในรูปคือวงกลมสามวง ได้แก่ สถานะ q0 q1 และ q2 ระหว่างสถานะเหล่านี้มีการเปลี่ยนสถานะ ซึ่งก็คือลูกศร นอกจากนี้ออโตมาตาต้องมีสถานะเริ่มต้น ซึ่งในที่นี้คือสถานะ q0 สถานะเริ่มต้นมักแสดงด้วยลูกศรที่ชี้เข้าหาสถานะนั้นโดยไม่ได้ออกมาจากสถานะใด ออโตมาตามักมีสถานะสิ้นสุด (สถานะยอมรับ) ด้วย ซึ่งแสดงด้วยเส้นคู่ ในรูปคือสถานะ q2
ออโตมาตาที่สร้างขึ้นเช่นนี้จะยอมรับสตริงบางสตริง เราป้อนสตริงเข้าไปในออโตมาตา แล้วออโตมาตาจะพยายามยอมรับสตริงนั้น ถ้ายอมรับ ออโตมาตาจะตอบว่า ใช่ ถ้าไม่ยอมรับ จะตอบว่า ไม่ใช่ ออโตมาตาในตัวอย่างนี้พยายามยอมรับสตริงที่ประกอบด้วยตัวอักษร “a” “b” และ “c” ดังนั้นลองป้อนสตริง “abbc”
เริ่มที่สถานะเริ่มต้น q0 และสตริงขาเข้าคือ “abbc” จากนั้นให้เดินตามลูกศร
อ่านสตริงตามปกติจากซ้ายไปขวา นั่นคือสัญลักษณ์แรกที่อ่านคือ “a” ลูกศรสำหรับ “a” ชี้ไปที่สถานะ q1 จึงเปลี่ยนไปที่สถานะนั้นและตัดสัญลักษณ์ “a” ออกจากสตริง สตริงขาเข้าที่เหลือคือ “bbc”:
ลูกศรสำหรับ “b” ชี้กลับมาที่ปม q1 ตัดตัวอักษรแรกออกอีกครั้ง สตริงขาเข้าที่เหลือคือ “bc” และยังคงอยู่ที่สถานะ q1 เช่นเดิม สุดท้ายสตริงขาเข้าที่เหลือคือ “c” จากสถานะ q1 ลูกศรสำหรับ “c” จะพาไปที่สถานะ q2
ตอนนี้อ่านตัวอักษรของสตริงขาเข้าครบทุกตัวแล้ว และอยู่ที่สถานะ q2 ซึ่งเป็นสถานะสิ้นสุด ดังนั้นออโตมาตาจำกัดนี้ยอมรับสตริง “abbc”
ถ้าเมื่ออ่านจบแล้วไม่ได้อยู่ในสถานะยอมรับ ออโตมาตาจะไม่ยอมรับสตริงนั้น ในทำนองเดียวกัน ออโตมาตาจะไม่ยอมรับสตริงถ้าถึงสถานะใดแล้วไม่มีทางไปต่อ เช่น สำหรับสตริง “ab” จะไปถึงสถานะ q1 แล้วจบที่นั่น ออโตมาตาจึงไม่ยอมรับสตริงนี้ ถ้าทดสอบสตริง “aabbc” ก็ไม่ได้เช่นกัน เพราะจากสถานะ q1 ไม่มีลูกศรสำหรับตัวอักษร “a”
ออโตมาตาจำกัดจึงใช้สำหรับจำแนกเซตของสตริงเซตหนึ่ง ในทางปฏิบัติอาจใช้ออโตมาตาตรวจสอบว่าสตริงขาเข้าที่กำหนดเป็นที่อยู่อีเมลที่ถูกต้องหรือไม่
นิยามของออโตมาตาจำกัด
แนวคิดเชิงสัญชาตญาณข้างต้นเกี่ยวกับออโตมาตาจำกัดต้องนำมาเขียนให้เป็นรูปนัย เพื่อให้ทำงานกับออโตมาตาต่อไปได้ดีขึ้น
ออโตมาตาจำกัด (แบบดีเทอร์มินิสติก) คือสิ่งอันดับ 5 สิ่ง ⟨Q, Σ, δ, q0, F⟩ โดยที่
- Q เป็นเซตจำกัดของสถานะ
- Σ (ซิกมาตัวใหญ่) เป็นอักษร (alphabet) คือเซตจำกัดของสัญลักษณ์หรือตัวอักษร
- δ: Q × Σ ⟶ Q เป็นฟังก์ชันการเปลี่ยนสถานะ (transition function)
- q0 ∈ Q เป็นสถานะเริ่มต้น
- F ⊆ Q เป็นเซตของสถานะสิ้นสุด (สถานะยอมรับ)
กลับไปที่ออโตมาตาก่อนหน้า
จะได้ว่าเซตของสถานะ Q มีสามสถานะ Q = {q0, q1, q2} อักษร Σ มีตัวอักษรที่ใช้สร้างสตริงซึ่งออโตมาตาจะยอมรับหรือปฏิเสธ ในที่นี้น่าจะเป็นอักษร Σ= {a, b, c} แต่อาจเป็นซูเปอร์เซตใดก็ได้ สถานะเริ่มต้น q0 คือสถานะ q0 ไม่มีอะไรเปลี่ยน เซตของสถานะสิ้นสุดในออโตมาตานี้มีเพียงสถานะเดียว F = {q2}
ฟังก์ชันการเปลี่ยนสถานะคือลูกศรสามเส้นที่มีตัวอักษรกำกับ ถ้าสัญลักษณ์ δ: Q × Σ ⟶ Q ดูสับสน ความหมายก็เพียงว่า δ เป็นฟังก์ชัน (หรือการส่ง) ที่รับพารามิเตอร์สองตัว คือสถานะจาก Q และตัวอักษรจาก Σ แล้วคืนค่าเป็นสถานะใหม่ ฟังก์ชันการเปลี่ยนสถานะของตัวอย่างนี้นิยามด้วยตารางได้ดังนี้:
ถ้าเรียกใช้ δ(q1, c) จะใช้แถวที่สาม และฟังก์ชันจะให้สถานะ q2 ซึ่งตรงกับแผนภาพ คือถ้าอยู่ที่สถานะ q1 และตัวอักษรขาเข้าคือ “c” จะเปลี่ยนไปที่สถานะ q2 ก่อนจะนิยามอย่างเป็นรูปนัยว่าออโตมาตายอมรับสตริงหมายความว่าอย่างไร จะใช้ความเข้าใจเชิงสัญชาตญาณของคำนี้ไปก่อน แล้วดูตัวอย่างเพิ่มเติม
ตัวอย่างเพิ่มเติม
-
จงสร้างออโตมาตาบนอักษรฐานสอง Σ= {0, 1} ที่ยอมรับเฉพาะสตริงที่ลงท้ายด้วยเลข 1 เช่น ยอมรับสตริง 1, 01, 000001, 0101011
ออโตมาตานี้มีสองสถานะ คือสถานะเริ่มต้น q0 และสถานะสิ้นสุด q1 เมื่อใดที่ขาเข้าเป็นเลข 1 จะเปลี่ยนไปที่สถานะสิ้นสุด q1 และอยู่ที่สถานะนั้น ในทางกลับกัน ถ้าขาเข้าเป็นเลข 0 จะเปลี่ยนไปที่สถานะ q0 ซึ่งไม่ใช่สถานะสิ้นสุด และอยู่ที่สถานะนั้นเช่นกัน
-
จงสร้างออโตมาตาบนอักษรฐานสองที่ยอมรับเฉพาะสตริงที่ตัวอักษรตัวแรกต่างจากตัวอักษรตัวสุดท้าย
ตั้งแต่ขั้นแรก ออโตมาตาแยกออกเป็น “ออโตมาตาย่อย” สองส่วน ถ้าสตริงขึ้นต้นด้วยเลข 0 ออโตมาตาจะเข้าสู่ส่วนซ้ายและอยู่ในส่วนนั้นตลอด ถ้าขึ้นต้นด้วยเลข 1 จะไปที่ส่วนขวา ส่วนที่เหลือก็ทำแบบเดิม ถ้าอยู่ในส่วนซ้ายและขาเข้าเป็น 1 จะเปลี่ยนไปที่สถานะสิ้นสุดและอยู่ที่นั่น ถ้าขาเข้าเป็น 0 จะเปลี่ยนไปที่สถานะ q1 ซึ่งไม่ใช่สถานะสิ้นสุด
ออโตมาตานี้ต่างจากออโตมาตาก่อนหน้าตรงที่มีสถานะสิ้นสุดมากกว่าหนึ่งสถานะ คือ F = {q3, q4}
-
จงสร้างออโตมาตาบนอักษรฐานสองที่ยอมรับเฉพาะสตริงที่ไม่มีเลข 0 สองตัวติดกัน
ออโตมาตานี้น่าสนใจด้วยเหตุผลสองข้อ ข้อแรกคือยอมรับสตริงว่าง ถ้าป้อนสตริงว่างเข้าไป ออโตมาตาจะยอมรับเมื่อสถานะเริ่มต้นเป็นสถานะสิ้นสุดด้วย ซึ่งเป็นเช่นนั้นในออโตมาตานี้ และเนื่องจากสตริงว่างไม่มีเลข 0 สองตัวติดกัน จึงถูกต้องแล้ว ข้อที่สองคือทุกสถานะของออโตมาตานี้เป็นสถานะสิ้นสุด กรณีเดียวที่ออโตมาตาจะไม่ยอมรับสตริงคือเมื่อไม่มีการเปลี่ยนสถานะออกจากสถานะปัจจุบัน ซึ่งเกิดขึ้นที่สถานะ q1 ที่ไม่มีการเปลี่ยนสถานะสำหรับ 0 เพราะถ้ามี สตริงจะมีเลข 0 สองตัวติดกัน
-
จงสร้างออโตมาตาบนอักษร {-,+,.,0,1,…,9} ที่ยอมรับเฉพาะสตริงที่แทนจำนวน นั่นคือจำนวนเต็ม เช่น 2, 548, 98263 หรือทศนิยม เช่น 5584.48, 3.14 ทั้งสองแบบมีรูปจำนวนลบที่มีเครื่องหมายลบ -2, -548, -3.14 และรูปที่เขียนเครื่องหมายบวกกำกับไว้ชัดเจน คือ +2, +548, +3.14 นอกจากนี้ต้องเขียนจำนวน 0.123 เป็น .123 (ไม่มีศูนย์นำหน้า) ได้ด้วย ทั้งแบบมีเครื่องหมายบวกและลบ เพื่อความสะดวก แทนที่จะเขียนการเปลี่ยนสถานะสิบเส้นสำหรับเลขโดดสิบตัว จะใช้สัญลักษณ์ N แทน
-
จงสร้างออโตมาตาบนอักษรฐานสองที่ยอมรับเฉพาะสตริงในรูป 0n1n ซึ่งหมายความว่าสตริงขึ้นต้นด้วยเลข 0 จำนวนหนึ่ง แล้วตามด้วยเลข 1 จำนวนเท่ากัน ตัวอย่างของสตริงเช่นนี้คือ 0011, 00001111, 01
ออโตมาตาเช่นนี้สร้างไม่ได้ เพราะไม่มีที่ใดให้ “จำ” จำนวนของเลข 0 ไว้ได้ หากจะทำ ต้องสร้าง “ออโตมาตาย่อย” หลายส่วนคล้ายกับในตัวอย่างที่สอง แต่ออโตมาตาย่อยเหล่านี้ต้องมีจำนวนมากมายไม่จำกัด คือหนึ่งส่วนสำหรับค่า n แต่ละค่า
การคำนวณของออโตมาตาในรูปนัย
ได้นิยามออโตมาตาจำกัดอย่างเป็นรูปนัยแล้ว ต่อไปต้องนิยามว่าออโตมาตาทำอะไร นั่นคือนิยามการคำนวณของออโตมาตา
รูปแบบของออโตมาตา (configuration): คู่อันดับ ⟨q, w⟩ ∈ Q × Σ∗ เรียกว่ารูปแบบของออโตมาตา โดยที่ q คือสถานะปัจจุบันของออโตมาตา และ w คือส่วนของสตริงที่ยังไม่ได้อ่าน Σ∗ แทนส่วนปิดคลุมของอักษร Σ ซึ่งเป็นเซตของสตริงทั้งหมดที่สร้างได้จากตัวอักษรของอักษร Σ ส่วนปิดคลุมนี้รวมสตริงว่างด้วย ซึ่งเขียนแทนด้วย ε
ถ้ามีออโตมาตา ⟨Q, Σ, δ, q0, F⟩ และต้องการให้ยอมรับสตริง w ออโตมาตาจะอยู่ในรูปแบบเริ่มต้น ⟨q0, w⟩ กลับไปที่ออโตมาตา
ถ้าต้องการให้ยอมรับสตริง w = abbc รูปแบบเริ่มต้นจะเป็น ⟨q0, abbc⟩
ขั้นของการคำนวณ นิยามเป็นความสัมพันธ์ ↦ บนเซต (Q × Σ∗) × (Q × Σ∗) นั่นคือระหว่างรูปแบบของออโตมาตา ให้ w = w0w1… wn แทนส่วนของสตริง w ที่ยังไม่ได้อ่าน คู่ ⟨q1, w0w1… wn⟩ และ ⟨q2, w1… wn⟩ มีความสัมพันธ์ ↦ ซึ่งเขียนว่า
ก็ต่อเมื่อ δ(q1, w0) = q2 กลับไปที่ตัวอย่าง รูปแบบเริ่มต้นคือ ⟨q0, abbc⟩ จากแผนภาพจะเห็นว่าสำหรับขาเข้า “a” เปลี่ยนไปที่สถานะ q1 ได้ จึงเขียนได้ว่า
เพราะ δ(q0, a) = q1 นี่คือการคำนวณหนึ่งขั้น คือดูว่าสำหรับขาเข้าที่กำหนด (ตัวอักษรตัวแรกของส่วนที่ยังไม่ได้อ่าน) ควรไปที่สถานะใด แล้วเปลี่ยนไปที่สถานะนั้น และตัดตัวอักษรตัวแรกออกจากส่วนที่ยังไม่ได้อ่าน จึงได้รูปแบบใหม่
ส่วนปิดคลุมสะท้อนและถ่ายทอด (reflexive and transitive closure) ของความสัมพันธ์ขั้นของการคำนวณเขียนแทนด้วย ↦ ∗ ถ้าเขียน K1 ↦ ∗ K2 โดยที่ K1, K2 เป็นรูปแบบของออโตมาตา หมายความว่าจากรูปแบบ K1 ไปถึงรูปแบบ K2 ได้ด้วยการคำนวณหลายขั้น หรือกล่าวอีกอย่างว่ามีลำดับจำกัดของรูปแบบที่:
เช่น ในออโตมาตาตัวอย่าง ⟨q0, abbc⟩ ↦ ∗ ⟨q1,bc⟩ เพราะเมื่อคำนวณสองขั้น จะเหลือสตริง “bc” และอยู่ที่สถานะ q1 นั่นคือมีลำดับของรูปแบบดังนี้:
ออโตมาตายอมรับสตริง w ก็ต่อเมื่อมี qf ∈ F ที่ทำให้
และสถานะ q2 เป็นสถานะสิ้นสุด q2 ∈ F
ภาษาที่ออโตมาตายอมรับ คือเซตของสตริงทั้งหมดที่ออโตมาตายอมรับ ภาษาของออโตมาตา A เขียนแทนด้วย L(A) ดังนั้น L(A) ⊆ Σ∗ และ
ภาษาปรกติ (regular language) คือภาษาที่ออโตมาตาจำกัดบางตัวยอมรับ
ออโตมาตาจำกัดสองตัวสมมูลกัน ถ้ายอมรับภาษาเดียวกัน นั่นคือออโตมาตา A1 และ A2 สมมูลกันถ้า L(A1) = L(A2)
แหล่งอ้างอิง
สารบัญ: ออโตมาตาจำกัด, ออโตมาตาที่สมบูรณ์, ออโตมาตาจำกัดแบบนอนดีเทอร์มินิสติก, การจำลองออโตมาตาแบบนอนดีเทอร์มินิสติก, การแปลง NFA เป็น DFA