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

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

Definition

ลำดับชั้นของชอมสกีเป็นการจำแนกไวยากรณ์เชิงรูปนัยโดยการใช้ข้อจำกัดที่เข้มงวดขึ้นเรื่อยๆ กับกฎการสร้าง (production rules) ซึ่งก่อให้เกิดภาษาประเภทปกติ (regular), ภาษาไม่ขึ้นกับบริบท (context-free), ภาษาขึ้นกับบริบท (context-sensitive) และภาษาที่แจงนับได้แบบเรียกซ้ำ (recursively enumerable) ในลักษณะของการบรรจุที่เข้มงวด

Scope

หัวข้อนี้ครอบคลุมไวยากรณ์สี่ประเภท ได้แก่ แบบไม่จำกัด (unrestricted), แบบขึ้นกับบริบท (context-sensitive), แบบไม่ขึ้นกับบริบท (context-free) และแบบปกติ (regular) รวมถึงการบรรจุที่เข้มงวดของแต่ละประเภท และแบบจำลองออโตมาตอนที่สอดคล้องกับแต่ละระดับ ได้แก่ เครื่องจักรทัวริง (Turing machine), ออโตมาตอนแบบจำกัดเชิงเส้น (linear-bounded automaton), พุชดาวน์ออโตมาตอน (pushdown automaton) และไฟไนต์ออโตมาตอน (finite automaton) พร้อมด้วยคุณสมบัติการปิด (closure) และการตัดสินใจได้ (decidability) ที่แยกแต่ละระดับออกจากกัน

Core questions

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

Key theories

การจับคู่ไวยากรณ์–เครื่องจักร

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

การบรรจุที่เข้มงวดของประเภทภาษา

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

Clinical relevance

ลำดับชั้นนี้เป็นแผนที่จัดระเบียบของทฤษฎีภาษาเชิงรูปนัย: มันบอกนักออกแบบภาษาโปรแกรม, ภาษาคิวรี, และข้อกำหนดโปรโตคอลว่ารูปแบบที่กำหนดต้องการกลไกมากน้อยเพียงใด และมันกำหนดขอบเขตระหว่างสิ่งที่ตัดสินใจได้ (decidable) และสิ่งที่เพียงแค่จดจำได้ (recognizable)

History

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

Key figures

• Noam Chomsky
• Marcel-Paul Schützenberger
• John Myhill

Seminal works

• hopcroft2006
• sipser2013

Frequently asked questions

ลำดับชั้นของชอมสกีมีกี่ระดับ?

จากน้อยไปมาก ได้แก่ ภาษาปกติ (ประเภท 3), ภาษาไม่ขึ้นกับบริบท (ประเภท 2), ภาษาขึ้นกับบริบท (ประเภท 1) และภาษาที่แจงนับได้แบบเรียกซ้ำ (ประเภท 0) แต่ละระดับจะผ่อนคลายข้อจำกัดของกฎไวยากรณ์และสอดคล้องกับเครื่องจักรที่มีหน่วยความจำมากขึ้น

ภาษาธรรมชาติถูกครอบคลุมโดยลำดับชั้นของชอมสกีหรือไม่?

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