Automata Theory: คำศัพท์และการใช้งาน

ในยุคเทคโนโลยีปัจจุบันทั้งด้านฮาร์ดแวร์และซอฟต์แวร์ได้เห็นการพัฒนาอย่างมาก หนึ่งในประเด็นสำคัญของการพัฒนาคือวิธีการออกแบบฮาร์ดแวร์ กับ เทคโนโลยีที่กำลังเติบโต แนวคิดของฮาร์ดแวร์ - การออกแบบซอฟต์แวร์ร่วมกันสามารถนำไปใช้ได้ วิธีการต่างๆได้รับการพัฒนาโดย โดยใช้ซอฟต์แวร์ สามารถออกแบบและจำลองระบบฮาร์ดแวร์ได้อย่างเต็มที่ หนึ่งในวิธีดังกล่าวคือ 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 มีมาตั้งแต่สมัยก่อนประวัติศาสตร์ ด้วยการคิดค้นเทคโนโลยีใหม่ ๆ มีการพัฒนาใหม่ ๆ มากมายในสาขานี้ คุณเจอออโตมาตะประเภทไหน