ทฤษฎีภาษาเชิงรูปนัยและออโตมาตา

ทฤษฎีภาษาเชิงรูปนัยและเครื่องจักรนามธรรมที่สามารถจดจำภาษานั้นได้ ซึ่งเป็นรากฐานในการอธิบายความซับซ้อนของรูปแบบทางภาษาและอัลกอริทึมที่สามารถประมวลผลได้

Definition

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

Scope

ครอบคลุมลำดับชั้นของชอมสกี (Chomsky hierarchy) (ภาษาเรกูลาร์ (regular), ภาษาคอนเท็กซ์ฟรี (context-free), ภาษาคอนเท็กซ์เซนซิทีฟ (context-sensitive), ภาษาที่แจงนับได้แบบเรียกซ้ำ (recursively enumerable languages)), ไวยากรณ์ที่เกี่ยวข้อง, และออโตมาตาที่ใช้ในการจดจำ — เครื่องสถานะจำกัด (finite-state machines), พุชดาวน์ออโตมาตา (pushdown automata), และเครื่องจักรทัวริง (Turing machines) นอกจากนี้ยังกล่าวถึงคุณสมบัติการปิด (closure properties) และคุณสมบัติการตัดสินใจได้ (decidability properties) ที่เกี่ยวข้องกับการประมวลผลภาษา และคำถามที่ว่าภาษาธรรมชาติอยู่ในลำดับชั้นใด สำหรับบทพิสูจน์ Pumping lemmas และความซับซ้อนฉบับเต็มจะถือเป็นเนื้อหาเสริมมากกว่าเนื้อหาหลัก

Core questions

• ออโตมาตาใดที่สอดคล้องกับแต่ละระดับของลำดับชั้นของชอมสกี?
• ภาษาธรรมชาติอยู่ในลำดับชั้นใด และเหตุใดจึงมีการโต้แย้งว่ามีพลังในการประมวลผลเกินกว่าคอนเท็กซ์ฟรี?
• การที่คลาสของภาษามีคุณสมบัติการปิดภายใต้การดำเนินการหมายความว่าอย่างไร และเหตุใดจึงมีความสำคัญต่องานวิศวกรรม?

Key concepts

• ภาษาเรกูลาร์
• ไวยากรณ์คอนเท็กซ์ฟรี
• ไวยากรณ์คอนเท็กซ์เซนซิทีฟ
• เครื่องสถานะจำกัด
• พุชดาวน์ออโตมาตา
• เครื่องจักรทัวริง
• คุณสมบัติการปิด
• คอนเท็กซ์เซนซิทีฟอย่างอ่อน

Key theories

ลำดับชั้นของชอมสกี

ภาษาเชิงรูปนัยสี่คลาสที่ซ้อนกัน แต่ละคลาสสร้างขึ้นโดยไวยากรณ์ประเภทที่จำกัดและจดจำโดยออโตมาตาที่สอดคล้องกัน ซึ่งจัดลำดับโครงสร้างทางภาษาตามพลังการคำนวณที่จำเป็น

ความสอดคล้องระหว่างไวยากรณ์และออโตมาตา

แต่ละคลาสของไวยากรณ์สามารถพิสูจน์ได้ว่าเทียบเท่ากับคลาสของเครื่องจักร — ไวยากรณ์เรกูลาร์เทียบเท่ากับออโตมาตาจำกัด, ไวยากรณ์คอนเท็กซ์ฟรีเทียบเท่ากับพุชดาวน์ออโตมาตา — ซึ่งเชื่อมโยงคำอธิบายเชิงกำเนิดเข้ากับอัลกอริทึมการจดจำ

History

บทความของชอมสกีในปี 1956 ได้นำเสนอแนวคิดลำดับชั้นนี้เพื่อโต้แย้งว่าแบบจำลองสถานะจำกัดไม่เพียงพอสำหรับภาษาธรรมชาติ ทศวรรษต่อมาได้มีการกำหนดความสัมพันธ์ระหว่างออโตมาตาอย่างเป็นทางการ และนักภาษาศาสตร์คอมพิวเตอร์ในภายหลังได้แสดงให้เห็นว่าภาษาธรรมชาติอย่างมากที่สุดต้องการพลังในการประมวลผลแบบ 'คอนเท็กซ์เซนซิทีฟอย่างอ่อน' (mildly context-sensitive) ซึ่งเป็นแรงจูงใจในการพัฒนาไวยากรณ์รูปแบบอื่นนอกเหนือจากคอนเท็กซ์ฟรี

Debates

ภาษาธรรมชาติเป็นภาษาคอนเท็กซ์ฟรีหรือไม่?

การพึ่งพาระหว่างส่วนประกอบข้ามกัน (cross-serial dependencies) ในภาษาต่างๆ เช่น ภาษาเยอรมันสวิส ถูกนำมาใช้เพื่อโต้แย้งว่าภาษาธรรมชาติมีพลังในการประมวลผลเกินกว่าคอนเท็กซ์ฟรี ซึ่งนำไปสู่แนวคิดเรื่องคอนเท็กซ์เซนซิทีฟอย่างอ่อนว่าเป็นระดับความสามารถในการแสดงออกที่เหมาะสม

Key figures

• Noam Chomsky
• John Hopcroft
• Jeffrey Ullman
• Stephen Kleene

Seminal works

• chomsky1956
• hopcroft2006

Frequently asked questions

ความแตกต่างระหว่างภาษาเรกูลาร์และภาษาคอนเท็กซ์ฟรีคืออะไร?

ภาษาเรกูลาร์สามารถจดจำได้ด้วยหน่วยความจำจำกัดโดยเครื่องสถานะจำกัด; ภาษาคอนเท็กซ์ฟรีอาจต้องใช้สแต็ก (พุชดาวน์ออโตมาตา) เพื่อติดตามโครงสร้างที่ซ้อนกัน เช่น วงเล็บที่สมดุลหรืออนุประโยคที่ฝังอยู่