ออโตมาตา (automata) หรือ เครื่องจักรกลอัตโนมัติ

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

ออโตมาตา รูปพหูพจน์ ออโตมาตา (automata), รูปเอกพจน์ ออโตมาตอน (automaton)

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

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