✖

ออโตมาตาจำกัด

ออโตมาตาจำกัด (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 และตัวอักษรจาก Σ แล้วคืนค่าเป็นสถานะใหม่ ฟังก์ชันการเปลี่ยนสถานะของตัวอย่างนี้นิยามด้วยตารางได้ดังนี้:

QΣ→Qq0aq1q1bq1q1cq2

ถ้าเรียกใช้ δ(q1, c) จะใช้แถวที่สาม และฟังก์ชันจะให้สถานะ q2 ซึ่งตรงกับแผนภาพ คือถ้าอยู่ที่สถานะ q1 และตัวอักษรขาเข้าคือ “c” จะเปลี่ยนไปที่สถานะ q2 ก่อนจะนิยามอย่างเป็นรูปนัยว่าออโตมาตายอมรับสตริงหมายความว่าอย่างไร จะใช้ความเข้าใจเชิงสัญชาตญาณของคำนี้ไปก่อน แล้วดูตัวอย่างเพิ่มเติม

ตัวอย่างเพิ่มเติม

  1. จงสร้างออโตมาตาบนอักษรฐานสอง Σ= {0, 1} ที่ยอมรับเฉพาะสตริงที่ลงท้ายด้วยเลข 1 เช่น ยอมรับสตริง 1, 01, 000001, 0101011

    ออโตมาตานี้มีสองสถานะ คือสถานะเริ่มต้น q0 และสถานะสิ้นสุด q1 เมื่อใดที่ขาเข้าเป็นเลข 1 จะเปลี่ยนไปที่สถานะสิ้นสุด q1 และอยู่ที่สถานะนั้น ในทางกลับกัน ถ้าขาเข้าเป็นเลข 0 จะเปลี่ยนไปที่สถานะ q0 ซึ่งไม่ใช่สถานะสิ้นสุด และอยู่ที่สถานะนั้นเช่นกัน

  2. จงสร้างออโตมาตาบนอักษรฐานสองที่ยอมรับเฉพาะสตริงที่ตัวอักษรตัวแรกต่างจากตัวอักษรตัวสุดท้าย

    ตั้งแต่ขั้นแรก ออโตมาตาแยกออกเป็น “ออโตมาตาย่อย” สองส่วน ถ้าสตริงขึ้นต้นด้วยเลข 0 ออโตมาตาจะเข้าสู่ส่วนซ้ายและอยู่ในส่วนนั้นตลอด ถ้าขึ้นต้นด้วยเลข 1 จะไปที่ส่วนขวา ส่วนที่เหลือก็ทำแบบเดิม ถ้าอยู่ในส่วนซ้ายและขาเข้าเป็น 1 จะเปลี่ยนไปที่สถานะสิ้นสุดและอยู่ที่นั่น ถ้าขาเข้าเป็น 0 จะเปลี่ยนไปที่สถานะ q1 ซึ่งไม่ใช่สถานะสิ้นสุด

    ออโตมาตานี้ต่างจากออโตมาตาก่อนหน้าตรงที่มีสถานะสิ้นสุดมากกว่าหนึ่งสถานะ คือ F = {q3, q4}

  3. จงสร้างออโตมาตาบนอักษรฐานสองที่ยอมรับเฉพาะสตริงที่ไม่มีเลข 0 สองตัวติดกัน

    ออโตมาตานี้น่าสนใจด้วยเหตุผลสองข้อ ข้อแรกคือยอมรับสตริงว่าง ถ้าป้อนสตริงว่างเข้าไป ออโตมาตาจะยอมรับเมื่อสถานะเริ่มต้นเป็นสถานะสิ้นสุดด้วย ซึ่งเป็นเช่นนั้นในออโตมาตานี้ และเนื่องจากสตริงว่างไม่มีเลข 0 สองตัวติดกัน จึงถูกต้องแล้ว ข้อที่สองคือทุกสถานะของออโตมาตานี้เป็นสถานะสิ้นสุด กรณีเดียวที่ออโตมาตาจะไม่ยอมรับสตริงคือเมื่อไม่มีการเปลี่ยนสถานะออกจากสถานะปัจจุบัน ซึ่งเกิดขึ้นที่สถานะ q1 ที่ไม่มีการเปลี่ยนสถานะสำหรับ 0 เพราะถ้ามี สตริงจะมีเลข 0 สองตัวติดกัน

  4. จงสร้างออโตมาตาบนอักษร {-,+,.,0,1,…,9} ที่ยอมรับเฉพาะสตริงที่แทนจำนวน นั่นคือจำนวนเต็ม เช่น 2, 548, 98263 หรือทศนิยม เช่น 5584.48, 3.14 ทั้งสองแบบมีรูปจำนวนลบที่มีเครื่องหมายลบ -2, -548, -3.14 และรูปที่เขียนเครื่องหมายบวกกำกับไว้ชัดเจน คือ +2, +548, +3.14 นอกจากนี้ต้องเขียนจำนวน 0.123 เป็น .123 (ไม่มีศูนย์นำหน้า) ได้ด้วย ทั้งแบบมีเครื่องหมายบวกและลบ เพื่อความสะดวก แทนที่จะเขียนการเปลี่ยนสถานะสิบเส้นสำหรับเลขโดดสิบตัว จะใช้สัญลักษณ์ N แทน

  5. จงสร้างออโตมาตาบนอักษรฐานสองที่ยอมรับเฉพาะสตริงในรูป 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,w0w1…wn⟩↦⟨q2,w1…wn⟩

ก็ต่อเมื่อ δ(q1, w0) = q2 กลับไปที่ตัวอย่าง รูปแบบเริ่มต้นคือ ⟨q0, abbc⟩ จากแผนภาพจะเห็นว่าสำหรับขาเข้า “a” เปลี่ยนไปที่สถานะ q1 ได้ จึงเขียนได้ว่า

⟨q0,abbc⟩↦⟨q1,bbc⟩

เพราะ δ(q0, a) = q1 นี่คือการคำนวณหนึ่งขั้น คือดูว่าสำหรับขาเข้าที่กำหนด (ตัวอักษรตัวแรกของส่วนที่ยังไม่ได้อ่าน) ควรไปที่สถานะใด แล้วเปลี่ยนไปที่สถานะนั้น และตัดตัวอักษรตัวแรกออกจากส่วนที่ยังไม่ได้อ่าน จึงได้รูปแบบใหม่

ส่วนปิดคลุมสะท้อนและถ่ายทอด (reflexive and transitive closure) ของความสัมพันธ์ขั้นของการคำนวณเขียนแทนด้วย ↦ ∗ ถ้าเขียน K1 ↦ ∗ K2 โดยที่ K1, K2 เป็นรูปแบบของออโตมาตา หมายความว่าจากรูปแบบ K1 ไปถึงรูปแบบ K2 ได้ด้วยการคำนวณหลายขั้น หรือกล่าวอีกอย่างว่ามีลำดับจำกัดของรูปแบบที่:

K1↦K11↦K12↦K13↦⋯↦K2

เช่น ในออโตมาตาตัวอย่าง ⟨q0, abbc⟩ ↦ ∗ ⟨q1,bc⟩ เพราะเมื่อคำนวณสองขั้น จะเหลือสตริง “bc” และอยู่ที่สถานะ q1 นั่นคือมีลำดับของรูปแบบดังนี้:

⟨q0,abbc⟩↦⟨q1,bbc⟩↦⟨q1,bc⟩

ออโตมาตายอมรับสตริง w ก็ต่อเมื่อมี qf ∈ F ที่ทำให้ ⟨q0,w⟩↦∗⟨qf,ε⟩ นั่นคือ ออโตมาตายอมรับสตริง w ก็ต่อเมื่อมีลำดับของขั้นการคำนวณซึ่งเมื่อจบลำดับแล้ว อ่านสตริงครบทั้งสตริงและอยู่ที่สถานะสิ้นสุดของออโตมาตา การที่อ่านสตริงครบแล้วแสดงด้วยการที่ตำแหน่งของสตริงในรูปแบบเป็น ε ซึ่งคือสตริงว่าง ออโตมาตาตัวอย่างยอมรับสตริง abbc เพราะมีลำดับของรูปแบบดังนี้:

⟨q0,abbc⟩↦⟨q1,bbc⟩↦⟨q1,bc⟩↦⟨q1,c⟩↦⟨q2,ε⟩

และสถานะ q2 เป็นสถานะสิ้นสุด q2 ∈ F

ภาษาที่ออโตมาตายอมรับ คือเซตของสตริงทั้งหมดที่ออโตมาตายอมรับ ภาษาของออโตมาตา A เขียนแทนด้วย L(A) ดังนั้น L(A) ⊆ Σ∗ และ

L(A)={w∈Σ∗|A ยอมรับสตริง w}

ภาษาปรกติ (regular language) คือภาษาที่ออโตมาตาจำกัดบางตัวยอมรับ

ออโตมาตาจำกัดสองตัวสมมูลกัน ถ้ายอมรับภาษาเดียวกัน นั่นคือออโตมาตา A1 และ A2 สมมูลกันถ้า L(A1) = L(A2)

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

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