ทฤษฎีออโตมาตา (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.
แต่ละหมวดหมู่ของภาษา ยกเว้นอันที่มีดาวติดอยู่ (* ) เป็นเซตย่อยแท้ ของหมวดหมู่ที่อยู่ด้านบนโดยตรง ทุกภาษาในแต่ละหมวดหมู่ถูกผลิตโดยไวยากรณ์และออโตมาตอนในหมวดหมู่บรรทัดเดียวกัน
