Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
ทฤษฎีออโตมาตา (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. . 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.
แหล่งข้อมูลอื่น
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
thvsdixxotmata Automata theory epnsakhahnungkhxngwithyakarkhxmphiwetxrthisuksaekhruxngckrsthanacakd phanthangwtthuthangkhnitsastrthiaesdngekhruxngckrehlannxxotmataxxotmata rupphhuphcn xxotmata automata rupexkphcn xxotmatxn automaton khwamhmayodytwsphthhmaythung sungekhluxnthihruxthanganiddwytnexng insakhawithyakarkhxmphiwetxrnn ichxxotmata ephuxepnomedlthangkhnitsastrkhxng ekhruxngckrsthanacakd raylaexiydphunthan xxotmatannepnomedlthangkhnitsastrkhxngekhruxngckrsthanacakd Finite state machine ekhruxngckrsthanacakdnn khuxekhruxngckrthiemuxrbkhxmul ca kraodd ipmarahwangsthanatang tamthiidrabuiwin fngkchnkarepliynaeplng sungsamarthekhiynxyuinrupkhxngtarangid sahrbekhruxngckrtrakul milli fngkchndngklawcarabusthanathicaepliynip sahrbsthanatngtn aelakhxmulthiidrb khxmulpxnekhacathuk xan thilatwxksr cnkrathngkhxmulthukxanekhaipthnghmd caekhaicidngaykhunthamxngkhxmulpxnekhaepnethpthimitwxksrekhiyneriyngtxknbnethpnn ethpnicathukxanodyhwxankhxngxxotmata sungcaxantwxksriperuxy khrnglahnungtwxksr emuxkhxmulthukxanekhaipcnhmd eracaklawwaxxotmatahyudthangan aelasthanakhxngmnkcaichbxkwaxxotmatann rb hrux imrb khxmulpxnekhann klawkhux thaxxotmatamisthanaxyuin sthanarb eracaklawwaxxotmata rb khxmulnn aelainthangklbkneracaklawwaxxotmata imrb khxmulnn erasamarthmxngwakhxmulpxnekhaid epn kha khahnung aelaeracaklawwaestkhxngkhathixxotmatarbepn phasathirbodyxxotmata nn khunlksnakhxngxxotmata prakxbdwysthana states fngkchnkarepliynsthana transition function sthanaerimtn initial states aela sthanakaryxmrb accepting states rbxinphutcakphaynxkrabbekhaxyangtxenuxng eriykxinphutthirbekhamaniwatwxksr alphabets ladbkhxngtwxksrthiepnxinphutsungrbekhamaeruxy nn eriykwa kha words mikarepliynsthanatamthikahndodyfngkchnkarepliynsthana xnepniptamtwxksrthirbxinphutekhama emuxhyudkarrbxinphut hakxxotmataxyuinsthanakaryxmrb thuxwaxxotmatayxmrbkhathiepnxinphutnn aetthaxxotmataxyunxksthanakaryxmrb thuxwaxxotmataptiesthkhathiepnxinphutnn estkhxngkhathnghmdthixxotmatannyxmrberiykwa phasa sungyxmrbodyxxotmatannpraephthkhxngxxotmataxxotmataechingkahnd Deterministic Finite Automata DFA xxotmataechingimkahnd Nondeterministic Finite Automata NFA xxotmataechingimkahnd thimikarepliynsthanadwyxksr e xksrwangepla Nondeterministic Finite Automata with e transitions e NFA phuchdawn xxotmata Pushdown Automata PDA ekhruxngkhanwnthwring Turing Machines xxotmataaebbmikhxbekhtechingesn Linear Bound Automata LBA xangxingMichael 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 aehlngkhxmulxun