ออโตมาตาและภาษาเชิงรูปนัย
ทฤษฎีออโตมาตาและภาษาเชิงรูปนัยศึกษาเครื่องจักรในอุดมคติที่มีกำลังเพิ่มขึ้นและคลาสของสายอักขระ หรือภาษา ที่แต่ละเครื่องจักรสามารถจดจำได้ ซึ่งให้คำอธิบายทางคณิตศาสตร์ที่แม่นยำว่าอะไรคือรูปแบบและต้องใช้อะไรในการตรวจจับรูปแบบนั้น
Definition
ภาษาเชิงรูปนัยคือชุดของสายอักขระจำกัดบนตัวอักษรที่กำหนดไว้ และออโตมาตาคืออุปกรณ์คอมพิวเตอร์เชิงนามธรรมที่การคำนวณที่ยอมรับได้กำหนดภาษาดังกล่าว; สาขานี้จำแนกภาษาตามประเภทที่ง่ายที่สุดของออโตมาตาหรือไวยากรณ์ที่สร้างหรือจดจำภาษาเหล่านั้น
Scope
สาขานี้ครอบคลุมออโตมาตาจำกัดและภาษาปกติ, พุชดาวน์ออโตมาตาและภาษาปราศจากบริบท, ลำดับชั้นของชอมสกีที่เชื่อมโยงไวยากรณ์เข้ากับแบบจำลองเครื่องจักร, คุณสมบัติการปิดและการตัดสินใจของคลาสภาษา, และออโตมาตาที่ประมวลผลคำและต้นไม้ที่ไม่มีที่สิ้นสุด พร้อมด้วยลักษณะเฉพาะทางพีชคณิตและตรรกะที่มาพร้อมกับสิ่งเหล่านั้น
Sub-topics
Core questions
- เครื่องจักรที่มีหน่วยความจำจำกัดสามารถจดจำภาษาใดได้บ้าง และไม่สามารถจดจำภาษาใดได้บ้าง?
- ไวยากรณ์และแบบจำลองเครื่องจักรมีความสัมพันธ์กันอย่างไรในแต่ละระดับของลำดับชั้นของชอมสกี?
- คำถามใดบ้างเกี่ยวกับคลาสภาษา เช่น ความว่างเปล่าหรือความสมมูล สามารถตัดสินใจได้ด้วยอัลกอริทึม?
- ออโตมาตาขยายไปสู่คำและต้นไม้ที่ไม่มีที่สิ้นสุดได้อย่างไร และเหตุใดสิ่งนี้จึงมีความสำคัญต่อการตรวจสอบ?
Key theories
- ความสมมูลของออโตมาตาจำกัดเชิงกำหนดและไม่กำหนด
- ออโตมาตาจำกัดแบบไม่กำหนดทุกตัวสามารถแปลงโดยการสร้างเซตย่อย (subset construction) ให้เป็นออโตมาตาเชิงกำหนดที่ยอมรับภาษาเดียวกันได้ ดังนั้นการไม่กำหนดจึงไม่ได้เพิ่มความสามารถในการจดจำในระดับสถานะจำกัด แม้ว่าอาจจะกระชับกว่ามากในเชิงเลขชี้กำลังก็ตาม
- ทฤษฎีของ Kleene
- ภาษาที่ออโตมาตาจำกัดจดจำได้นั้นเป็นภาษาปกติที่อธิบายโดยนิพจน์ปกติอย่างแท้จริง ซึ่งเชื่อมโยงมุมมองเชิงเครื่องจักร, พีชคณิต, และไวยากรณ์ของคลาสภาษาที่ง่ายที่สุดเข้าด้วยกัน
- ลำดับชั้นของชอมสกี
- ภาษาปกติ, ภาษาปราศจากบริบท, ภาษาที่ขึ้นกับบริบท, และภาษาที่แจงนับได้แบบเรียกซ้ำ (recursively enumerable languages) ก่อให้เกิดสายโซ่การรวมที่เข้มงวด โดยแต่ละระดับจะจับคู่กับประเภทไวยากรณ์และแบบจำลองออโตมาตาที่มีโครงสร้างหน่วยความจำที่สอดคล้องกัน
Clinical relevance
ออโตมาตาจำกัดและนิพจน์ปกติขับเคลื่อนการวิเคราะห์คำศัพท์ในคอมไพเลอร์, การค้นหาข้อความ, และการกำหนดโปรโตคอล, ในขณะที่ไวยากรณ์ปราศจากบริบทเป็นพื้นฐานของการแยกวิเคราะห์ภาษาโปรแกรม; ออโตมาตาบนวัตถุอนันต์เป็นแกนหลักเชิงอัลกอริทึมของการตรวจสอบแบบจำลอง (model checking) ซึ่งระบบจะได้รับการตรวจสอบเทียบกับข้อกำหนดตรรกะเชิงเวลา
History
แบบจำลองสถานะจำกัดเกิดขึ้นจากโครงข่ายประสาทของ McCulloch และ Pitts ในทศวรรษ 1940 และถูกกำหนดรูปแบบทางทฤษฎีภาษาโดย Kleene ประมาณปี 1951 Rabin และ Scott ได้นำเสนอออโตมาตาแบบไม่กำหนด (nondeterministic automata) ในปี 1959 ในขณะที่ไวยากรณ์ของ Chomsky จากปลายทศวรรษ 1950 ได้จัดระเบียบคลาสภาษาเป็นลำดับชั้นที่ยังคงเป็นโครงสร้างของวิชานี้
Key figures
- Stephen Kleene
- Michael Rabin
- Dana Scott
- Noam Chomsky
Related topics
Seminal works
- rabinScott1959
- sipser2013
- hopcroft2006
Frequently asked questions
- เหตุใดออโตมาตาจำกัดจึงไม่สามารถจดจำวงเล็บที่สมดุลได้?
- การจดจำการซ้อนกันที่ลึกโดยพลการต้องนับจำนวนวงเล็บเปิดที่ยังไม่ถูกจับคู่ ซึ่งอาจเกินจำนวนสถานะที่กำหนดไว้ ออโตมาตาจำกัดมีหน่วยความจำที่จำกัดเท่านั้น ดังนั้นความสามารถในการนับนี้จึงอยู่ในระดับที่สูงขึ้นหนึ่งระดับ คือกับพุชดาวน์ออโตมาตาและภาษาปราศจากบริบท
- ผลตอบแทนเชิงปฏิบัติของทฤษฎีภาษาเชิงรูปนัยคืออะไร?
- มันบอกวิศวกรว่าเครื่องมือที่กำหนดสามารถแสดงรูปแบบใดได้บ้าง นิพจน์ปกติเพียงพอสำหรับโทเค็นแต่ไม่เพียงพอสำหรับโครงสร้างที่ซ้อนกัน ซึ่งเป็นเหตุผลว่าทำไมคอมไพเลอร์จึงแบ่งงานระหว่างตัวแยกคำศัพท์ปกติ (regular lexer) และตัวแยกวิเคราะห์ปราศจากบริบท (context-free parser) และเหตุใดเครื่องมือตรวจสอบจึงอาศัยออโตมาตาบนคำที่ไม่มีที่สิ้นสุด