ในยุคเทคโนโลยีปัจจุบันทั้งด้านฮาร์ดแวร์และซอฟต์แวร์ได้เห็นการพัฒนาอย่างมาก หนึ่งในประเด็นสำคัญของการพัฒนาคือวิธีการออกแบบฮาร์ดแวร์ กับ เทคโนโลยีที่กำลังเติบโต แนวคิดของฮาร์ดแวร์ - การออกแบบซอฟต์แวร์ร่วมกันสามารถนำไปใช้ได้ วิธีการต่างๆได้รับการพัฒนาโดย โดยใช้ซอฟต์แวร์ สามารถออกแบบและจำลองระบบฮาร์ดแวร์ได้อย่างเต็มที่ หนึ่งในวิธีดังกล่าวคือ Automata Theory ทฤษฎีออโตมาตาเป็นสาขาของ วิทยาศาสตร์คอมพิวเตอร์ ที่เกี่ยวข้องกับการออกแบบโมเดลนามธรรมของอุปกรณ์คอมพิวเตอร์ซึ่งเป็นไปตามลำดับขั้นตอนที่กำหนดไว้ล่วงหน้าโดยอัตโนมัติ บทความนี้กล่าวถึงข้อมูลสั้น ๆ เกี่ยวกับการสอนออโตมาตะ
Automata Theory คืออะไร?
คำว่า Automata มาจากภาษากรีกซึ่งแปลว่า 'การแสดงด้วยตนเอง' Automaton คือแบบจำลองทางคณิตศาสตร์ของเครื่องจักร Automaton ประกอบด้วยสถานะและการเปลี่ยนแปลง เนื่องจากอินพุตถูกกำหนดให้กับออโตเมตันมันจะทำการเปลี่ยนไปสู่สถานะถัดไปขึ้นอยู่กับฟังก์ชันการเปลี่ยน อินพุตของฟังก์ชันการเปลี่ยนแปลงคือสถานะปัจจุบันและสัญลักษณ์ล่าสุด หาก Automaton มีสถานะจำนวน จำกัด จะเรียกว่า Finite Automata หรือ เครื่องไฟไนต์สเตท . ออโตมาตา จำกัด แสดงด้วย 5 ทูเพิล (Q, ∑, δ, qo, F)
ที่ไหน
Q = ชุดสถานะ จำกัด
∑ = ชุดสัญลักษณ์ที่ จำกัด เรียกอีกอย่างว่าตัวอักษรของออโตมาตา
δ = ฟังก์ชันการเปลี่ยนแปลง
qo = สถานะเริ่มต้นของอินพุต
F = ชุดของสถานะสุดท้ายของ Q
คำศัพท์พื้นฐานของทฤษฎีออโตมาตา
คำศัพท์พื้นฐานบางประการของ Automata Theory คือ -
1 . ตัวอักษร : ชุดสัญลักษณ์ที่ จำกัด ใด ๆ ในทฤษฎีออโตมาตาเรียกว่าตัวอักษร แทนด้วยตัวอักษรเซต {a, b, c, d, e,} เรียกว่าชุดตัวอักษรในขณะที่ตัวอักษรของชุด 'a', 'b', 'c', 'd', 'e' เรียกว่า สัญลักษณ์
สอง . สตริง : ในออโตมาตาสตริงคือลำดับที่ จำกัด ของสัญลักษณ์ที่นำมาจากชุดตัวอักษร ∑ ตัวอย่างเช่นสตริง S = 'adeaddadc' ใช้ได้กับชุดตัวอักษร ∑ = {a, b, c, d, e,}
3 . ความยาวของสตริง : จำนวนสัญลักษณ์ที่มีอยู่ในสตริงเรียกว่า Length of string สำหรับสตริง S = 'adaada' ความยาวของสตริงคือ | S | = 6. ถ้าความยาวของสตริงเป็น 0 จะเรียกว่าสตริงว่าง
4 . ไคลน์สตาร์ : เป็นตัวดำเนินการยูนารีบนชุดของสัญลักษณ์Σซึ่งให้ชุดของสตริงที่เป็นไปได้ทั้งหมดไม่สิ้นสุดรวมถึงλของความยาวทั้งหมดที่เป็นไปได้ในเซตΣ มันแสดงโดย. ตัวอย่างเช่นสำหรับเซตΣ = {c, d}, ∑ * = {λ, c, d, cd, dc, cc, dd, ……}
5 . คลีนปิด : เป็นชุดของสตริงที่เป็นไปได้ทั้งหมดของชุดตัวอักษรไม่รวมλ แสดงโดย สำหรับเซตΣ = {a, d}, ∑ + = {a, d, ad, da, aa, dd, … .. }
6 . ภาษา : ภาษาเป็นส่วนย่อยของชุดดาวคลีน * สำหรับชุดตัวอักษรบางตัวΣ ภาษาสามารถ จำกัด หรือไม่มีที่สิ้นสุด ตัวอย่างเช่นถ้าภาษาหนึ่งใช้สตริงความยาว 2 ที่เป็นไปได้ทั้งหมดทับเซตΣ = {a, d} แล้ว L = {aa, ad, da, dd}
ภาษาทางการและออโตมาตา
ในทฤษฎีออโตมาตาภาษาทางการคือชุดของสตริงโดยที่แต่ละสตริงอยู่ ประกอบด้วยสัญลักษณ์ เป็นของชุดอักษร จำกัด Σ ให้เราพิจารณาภาษาแมวซึ่งสามารถมีสตริงใดก็ได้จากชุดอนันต์ด้านล่าง ...
มิว!
มิวว์!
มิววว !! ……
ชุดตัวอักษรสำหรับภาษาแมวคือΣ = {m, e, w,!} ให้ชุดนี้ใช้สำหรับ Finite State Automata Model-m จากนั้นภาษาทางการที่มีรูปแบบ m จะแสดงด้วย
L (ม.)
L (m) = {‘mew!’, ‘meww!’, ‘mewww’, ……}
Automaton มีประโยชน์สำหรับการกำหนดภาษาเนื่องจากสามารถแสดงชุดที่ไม่มีที่สิ้นสุดในรูปแบบปิด ภาษาที่เป็นทางการไม่เหมือนกับภาษาธรรมชาติที่เราพูดกันในชีวิตประจำวัน ภาษาที่เป็นทางการสามารถแสดงสถานะต่างๆของเครื่องได้ซึ่งแตกต่างจากภาษาทั่วไปของเรา ภาษาที่เป็นทางการถูกใช้เพื่อสร้างแบบจำลองส่วนหนึ่งของภาษาธรรมชาติเช่นวากยสัมพันธ์เป็นต้น ... ภาษาทางการถูกกำหนดโดยออโตมาตา จำกัด มีสองมุมมองหลักของ Finite state automata- ตัวรับที่สามารถบอกได้ว่าสตริงอยู่ในภาษาหรือไม่และอันที่สองคือตัวสร้างที่สร้างเฉพาะสตริงในภาษา
Finite Automata ที่มุ่งมั่น
ในประเภทของออโตมาตาที่กำหนดเมื่อมีการป้อนข้อมูลเราสามารถกำหนดได้เสมอว่าการเปลี่ยนแปลงจะเป็นสถานะใด เนื่องจากนี่คือหุ่นยนต์ที่มีข้อ จำกัด จึงเรียกว่า Deterministic Finite Automata
การแสดงกราฟิก
State Diagram คือไดกราฟที่ใช้สำหรับการแสดงกราฟิกของ Deterministic Finite Automata ให้เราเข้าใจด้วยตัวอย่าง ให้ออโตมาตา จำกัด ที่กำหนดเป็น ...
ถาม = {a, b, c, d}
Σ = {0, 1}
= {a}
F = {d} และฟังก์ชันการเปลี่ยนเป็น
แบบฟอร์มตารางการแสดงกราฟิก
แผนภาพสถานะ
แผนภาพสถานะของ Automata สถานะ จำกัด ที่กำหนด
จากแผนภาพสถานะ
- สถานะจะแสดงด้วยจุดยอด
- การเปลี่ยนจะแสดงโดยส่วนโค้งที่มีป้ายกำกับด้วยตัวอักษรอินพุต
- ส่วนโค้งขาเข้าเดี่ยวที่ว่างเปล่าแสดงถึงสถานะเริ่มต้น
- สถานะที่มีวงกลมสองวงเป็นสถานะสุดท้าย
ออโตมาตา จำกัด แบบไม่กำหนด
ออโตมาตาที่ไม่สามารถกำหนดสถานะเอาต์พุตสำหรับอินพุตที่กำหนดได้เรียกว่า Non-Deterministic Automata เรียกอีกอย่างว่า Non-Deterministic Finite Automata เนื่องจากมีสถานะจำนวน จำกัด Finite Automata ที่ไม่ได้กำหนดจะแสดงเป็นชุดของ 5 –uple โดยที่ (Q, ∑, δ, qo, F)
ถาม = ชุดของรัฐที่ จำกัด
∑ = ชุดตัวอักษร
δ = ฟังก์ชันการเปลี่ยนแปลง
ที่ไหน : qo = สถานะเริ่มต้น
การแสดงกราฟิก
ออโตมาตา จำกัด แบบไม่กำหนดจะแสดงด้วยความช่วยเหลือของแผนภาพสถานะ ปล่อยให้ Finite Automata แบบไม่กำหนด -
ถาม = {a, b, c, d}
Σ = {0,1}
qo = {a}
F = {d}
การเปลี่ยนคือ
แบบฟอร์มตารางการแสดงกราฟิก
แผนภาพสถานะ
แผนภาพสถานะของ Automata จำกัด แบบไม่กำหนด
แอปพลิเคชั่น Automata Theory
การใช้งานของ ทฤษฎีออโตมาตา รวมสิ่งต่อไปนี้
- ทฤษฎีออโตมาตามีประโยชน์มากในด้านทฤษฎีการคำนวณการผลิตคอมไพเลอร์ AI เป็นต้น
- สำหรับคอมไพเลอร์ประมวลผลข้อความและการออกแบบฮาร์ดแวร์ออโตมาตา จำกัด มีบทบาทสำคัญ
- สำหรับการใช้งานใน AI และใน ภาษาโปรแกรม ไวยากรณ์ที่ไม่มีบริบทมีประโยชน์มาก
- ในสาขาชีววิทยา Cellular automata มีประโยชน์
- ในทางทฤษฎีของสาขา จำกัด เราสามารถพบการประยุกต์ใช้ Automata
ในบทความนี้เราได้เรียนรู้คำแนะนำสั้น ๆ เกี่ยวกับภาษาทฤษฎีออโตมาตาและการคำนวณ Automata มีมาตั้งแต่สมัยก่อนประวัติศาสตร์ ด้วยการคิดค้นเทคโนโลยีใหม่ ๆ มีการพัฒนาใหม่ ๆ มากมายในสาขานี้ คุณเจอออโตมาตะประเภทไหน