ทฤษฎีออโตมาตา

ทฤษฎีออโตมาตา (Automata theory) เป็นสาขาหนึ่งของวิทยาการคอมพิวเตอร์ที่ศึกษาเครื่องจักรสถานะจำกัด ผ่านทางวัตถุทางคณิตศาสตร์ที่แสดงเครื่องจักรเหล่านั้น

ออโตมาตา

ออโตมาตา รูปพหูพจน์ ออโตมาตา (automata), รูปเอกพจน์ ออโตมาตอน (automaton) ความหมายโดยตัวศัพท์หมายถึง เครื่องกลซึ่งเคลื่อนที่หรือทำงานได้ด้วยตนเอง. ในสาขาวิทยาการคอมพิวเตอร์นั้น ใช้ออโตมาตา เพื่อเป็นโมเดลทางคณิตศาสตร์ของ เครื่องจักรสถานะจำกัด

รายละเอียดพื้นฐาน

ออโตมาตานั้นเป็นโมเดลทางคณิตศาสตร์ของเครื่องจักรสถานะจำกัด (Finite state machine) เครื่องจักรสถานะจำกัดนั้น คือเครื่องจักรที่เมื่อรับข้อมูล จะ กระโดด ไปมาระหว่างสถานะต่าง ๆ ตามที่ได้ระบุไว้ใน ฟังก์ชันการเปลี่ยนแปลง ซึ่งสามารถเขียนอยู่ในรูปของตารางได้   สำหรับเครื่องจักรตระกูล "มีลลี" ฟังก์ชันดังกล่าวจะระบุสถานะที่จะเปลี่ยนไป สำหรับสถานะตั้งต้น และข้อมูลที่ได้รับ    ข้อมูลป้อนเข้าจะถูก "อ่าน" ทีละตัวอักษร จนกระทั่งข้อมูลถูกอ่านเข้าไปทั้งหมด (จะเข้าใจได้ง่ายขึ้นถ้ามองข้อมูลป้อนเข้าเป็นเทปที่มีตัวอักษรเขียนเรียงต่อกันบนเทปนั้น เทปนี้จะถูกอ่านโดยหัวอ่านของออโตมาตา ซึ่งจะอ่านตัวอักษรไปเรื่อย ๆ ครั้งละหนึ่งตัวอักษร)   เมื่อข้อมูลถูกอ่านเข้าไปจนหมด เราจะกล่าวว่าออโตมาตาหยุดทำงาน และสถานะของมันก็จะใช้บอกว่าออโตมาตานั้น รับ หรือ ไม่รับ ข้อมูลป้อนเข้านั้น   กล่าวคือ ถ้าออโตมาตามีสถานะอยู่ใน สถานะรับ เราจะกล่าวว่าออโตมาตา รับ ข้อมูลนั้น และในทางกลับกันเราจะกล่าวว่าออโตมาตา ไม่รับ ข้อมูลนั้น   เราสามารถมองว่าข้อมูลป้อนเข้าใด ๆ เป็น คำ คำหนึ่ง และเราจะกล่าวว่าเซตของคำที่ออโตมาตารับเป็น ภาษาที่รับโดยออโตมาตา นั้น

คุณลักษณะของออโตมาตา

• ประกอบด้วยสถานะ (states), ฟังก์ชันการเปลี่ยนสถานะ (transition function), สถานะเริ่มต้น (initial states) และ สถานะการยอมรับ (accepting states)
• รับอินพุตจากภายนอกระบบเข้าอย่างต่อเนื่อง เรียกอินพุตที่รับเข้ามานี้ว่าตัวอักษร (alphabets)
• ลำดับของตัวอักษรที่เป็นอินพุตซึ่งรับเข้ามาเรื่อย ๆ นั้น เรียกว่า คำ (words)
• มีการเปลี่ยนสถานะตามที่กำหนดโดยฟังก์ชันการเปลี่ยนสถานะ อันเป็นไปตามตัวอักษรที่รับอินพุตเข้ามา
• เมื่อหยุดการรับอินพุต หากออโตมาตาอยู่ในสถานะการยอมรับ ถือว่าออโตมาตายอมรับคำที่เป็นอินพุตนั้น แต่ถ้าออโตมาตาอยู่นอกสถานะการยอมรับ ถือว่าออโตมาตาปฏิเสธคำที่เป็นอินพุตนั้น
• เซตของคำทั้งหมดที่ออโตมาตานั้นยอมรับเรียกว่า ภาษา ซึ่งยอมรับโดยออโตมาตานั้น

ประเภทของออโตมาตา

• ออโตมาตาเชิงกำหนด (Deterministic Finite Automata; DFA)
• ออโตมาตาเชิงไม่กำหนด (Nondeterministic Finite Automata; NFA)
• ออโตมาตาเชิงไม่กำหนด ที่มีการเปลี่ยนสถานะด้วยอักษร ε (อักษรว่างเปล่า) (Nondeterministic Finite Automata, with ε transitions (ε-NFA))
• พุชดาวน์ ออโตมาตา (Pushdown Automata; PDA)
• เครื่องคำนวณทัวริ่ง (Turing Machines)
• ออโตมาตาแบบมีขอบเขตเชิงเส้น (Linear Bound Automata; LBA)

อ้างอิง

• Michael Sipser (1997). Introduction to the Theory of Computation, PWS Publishing. ISBN 0-534-94728-X. Part One: Automata and Languages, chapters 1–2, pp.29–122. Section 4.1: Decidable Languages, pp.152–159. Section 5.1: Undecidable Problems from Language Theory, pp.172–183.

แหล่งข้อมูลอื่น