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

ทฤษฎีออโตมาตา (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.

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

 

it:Automa (informatica)
simple:Automaton