ทฤษฎีออโตมาตา - วิกิพีเดีย

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

### จากวิกิพีเดีย สารานุกรมเสรี

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

## [แก้] ออโตมาตา

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

### [แก้] รายละเอียดพื้นฐาน

ออโตมาตานั้นเป็นโมเดลทางคณิตศาสตร์ของเครื่องจักรสถานะจำกัด (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)
- เครื่องคำนวณทัวริ่ง (Touring Machines)
- ออโตมาตาแบบมีขอบเขตเชิงเส้น (Linear Bound Automata; LBA)

^ รูปพหูพจน์ ออโตมาตา (automata), รูปเอกพจน์ ออโตมาตอน (automaton) – เนื่องจากภาษาไทยไม่มีการแบ่งคำนามพหูพจน์และเอกพจน์ ในที่นี้จะใช้คำว่าออโตมาตา ในการกล่าวถึงทั้ง automata และ automaton

## [แก้] ดูเพิ่มเติม

- บุชิ ออโตมาตา

| ทฤษฎีออโตมาตา เป็นบทความเกี่ยวกับ คณิตศาสตร์ ที่ยังไม่สมบูรณ์ ต้องการตรวจสอบ เพิ่มเนื้อหา หรือเพิ่มแหล่งอ้างอิง คุณสามารถช่วยเพิ่มเติมหรือแก้ไข เพื่อให้สมบูรณ์มากขึ้น

ข้อมูลเกี่ยวกับ ทฤษฎีออโตมาตา ในภาษาอื่น สามารถหาอ่านได้จากเมนู ภาษาอื่น ๆ ด้านซ้ายมือ
ดึงข้อมูลจาก "http://th.wikipedia.org../../../%E0%B8%97/%E0%B8%A4/%E0%B8%A9/%E0%B8%97%E0%B8%A4%E0%B8%A9%E0%B8%8E%E0%B8%B5%E0%B8%AD%E0%B8%AD%E0%B9%82%E0%B8%95%E0%B8%A1%E0%B8%B2%E0%B8%95%E0%B8%B2.html".

หมวดหมู่: ทฤษฎีการคำนวณ | ภาษารูปนัย | บทความเกี่ยวกับ คณิตศาสตร์ ที่ยังไม่สมบูรณ์

##### Views

- บทความ
- อภิปราย
- รุ่นปัจจุบัน

##### ค้นหา

##### ภาษาอื่น

- Deutsch
- English
- עברית
- Magyar
- Italiano
- 日本語
- Português
- Slovenčina