ลำดับชั้นของภาษาชอมสกี้คืออะไร และมันจำแนกไวยากรณ์ที่เป็นทางการอย่างไรตามพลังกำเนิดของมัน?
ลำดับชั้นของภาษา Chomsky เป็นระบบการจำแนกประเภทที่จัดหมวดหมู่ไวยากรณ์ที่เป็นทางการตามอำนาจกำเนิด เสนอโดย Noam Chomsky นักภาษาศาสตร์และนักวิทยาศาสตร์คอมพิวเตอร์ที่มีชื่อเสียงในทศวรรษที่ 1950 ลำดับชั้นประกอบด้วยสี่ระดับ แต่ละระดับแสดงถึงภาษาทางการที่แตกต่างกัน ระดับเหล่านี้เรียกว่า Type-3 (ปกติ), Type-2 (ไม่มีบริบท), Type-1 (ตามบริบท) และ Type-0 (ไม่จำกัด)
ที่ระดับต่ำสุดของลำดับชั้น เรามีภาษา Type-3 หรือที่เรียกว่าภาษาปกติ ภาษาเหล่านี้สามารถรับรู้โดยออโตมาตาจำกัด เช่น ออโตมาตาจำกัดที่กำหนดขึ้นได้และไม่ได้กำหนดกำหนด ภาษาปกติมีลักษณะเป็นนิพจน์ทั่วไปและไวยากรณ์ปกติ นิพจน์ทั่วไปคือนิพจน์เกี่ยวกับพีชคณิตที่อธิบายรูปแบบของสตริง ในขณะที่ไวยากรณ์ปกติประกอบด้วยกฎการผลิตที่สร้างสตริงในภาษาปกติ ตัวอย่างของภาษาปกติคือชุดของสตริงทั้งหมดที่ตรงกับนิพจน์ทั่วไปที่กำหนด เช่น ภาษาของสตริงไบนารีทั้งหมดที่มีเลข 0 เป็นเลขคู่
เมื่อเลื่อนลำดับชั้นขึ้นไป เราพบกับภาษาประเภทที่ 2 หรือที่เรียกว่าภาษาที่ไม่มีบริบท ภาษาเหล่านี้สามารถรับรู้ได้โดยออโตมาตาแบบกดลง ซึ่งเป็นออโตมาตาแบบจำกัดที่เสริมด้วยสแต็ก ภาษาที่ไม่มีบริบทอธิบายโดยไวยากรณ์ที่ไม่มีบริบท ซึ่งประกอบด้วยกฎการผลิตที่สร้างสตริงในภาษาที่ไม่มีบริบท ไวยากรณ์ที่ไม่มีบริบทมีสัญลักษณ์ที่ไม่ใช่เทอร์มินัล สัญลักษณ์เทอร์มินัล และกฎการผลิตที่ระบุวิธีการแทนที่อักขระที่ไม่ใช่เทอร์มินัลด้วยลำดับของสัญลักษณ์ ตัวอย่างของภาษาที่ไม่มีบริบทคือชุดของนิพจน์ทางคณิตศาสตร์ที่มีรูปแบบสมบูรณ์ โดยที่วงเล็บมีความสมดุลและมีการใช้ตัวดำเนินการอย่างถูกต้อง
ระดับถัดไปของลำดับชั้นคือภาษาประเภท 1 หรือที่เรียกว่าภาษาตามบริบท ภาษาเหล่านี้สามารถรับรู้โดยออโตมาตาที่มีขอบเขตเชิงเส้น ซึ่งเป็นออโตมาตาที่มีขอบเขตจำกัดด้วยเทปที่สามารถเคลื่อนที่ได้ทั้งสองทิศทาง ภาษาที่คำนึงถึงบริบทได้รับการอธิบายโดยไวยากรณ์ที่คำนึงถึงบริบท ซึ่งประกอบด้วยกฎการผลิตที่สร้างสตริงในภาษาที่คำนึงถึงบริบท ไวยากรณ์ตามบริบทมีข้อจำกัดเพิ่มเติมว่าความยาวของด้านขวามือของกฎการผลิตต้องไม่สั้นกว่าความยาวของด้านซ้ายมือ ตัวอย่างของภาษาที่คำนึงถึงบริบทคือชุดของพาลินโดรมทั้งหมด โดยที่สตริงอ่านไปข้างหน้าและข้างหลังเหมือนกัน
สุดท้าย ที่ด้านบนสุดของลำดับชั้น เรามีภาษา Type-0 หรือที่เรียกว่าภาษาไม่จำกัด ภาษาเหล่านี้สามารถรับรู้ได้โดยเครื่องทัวริงซึ่งเป็นอุปกรณ์คำนวณเชิงนามธรรมที่สามารถจำลองอัลกอริทึมของคอมพิวเตอร์ใดๆ ก็ได้ ภาษาที่ไม่จำกัดได้รับการอธิบายด้วยไวยากรณ์ที่ไม่จำกัด ซึ่งไม่มีข้อจำกัดเกี่ยวกับกฎการผลิต ตัวอย่างของภาษาที่ไม่จำกัดคือชุดของภาษาที่นับซ้ำได้ทั้งหมด ซึ่งรวมถึงภาษาที่คำนวณได้ทั้งหมด
ลำดับชั้นของภาษาชอมสกีเป็นกรอบที่เป็นระบบสำหรับการจำแนกไวยากรณ์ที่เป็นทางการตามอำนาจกำเนิด โดยเริ่มด้วยภาษาปกติซึ่งมีประสิทธิภาพน้อยที่สุด และพัฒนาไปสู่ภาษาที่ไม่มีบริบท คำนึงถึงบริบท และไม่ถูกจำกัด ซึ่งมีประสิทธิภาพมากขึ้นเรื่อยๆ ลำดับชั้นนี้เป็นแนวคิดพื้นฐานในด้านทฤษฎีความซับซ้อนทางการคำนวณ และมีความหมายที่สำคัญสำหรับการศึกษาภาษาทางการและออโตมาตา
คำถามและคำตอบล่าสุดอื่น ๆ เกี่ยวกับ ลำดับชั้นของ Chomsky และภาษาที่ละเอียดอ่อนตามบริบท:
- การที่ภาษาหนึ่งมีพลังมากกว่าอีกภาษาหนึ่งหมายความว่าอย่างไร?
- มีวิธีการรับรู้ Type-0 ในปัจจุบันหรือไม่? เราคาดหวังว่าคอมพิวเตอร์ควอนตัมจะทำให้เป็นไปได้หรือไม่?
- อธิบายขั้นตอนการออกแบบไวยากรณ์ที่คำนึงถึงบริบทสำหรับภาษาที่ประกอบด้วยสตริงที่มีจำนวนหนึ่ง สอง และสามเท่ากัน
- ยกตัวอย่างภาษาที่คำนึงถึงบริบทและอธิบายว่าไวยากรณ์ที่คำนึงถึงบริบทสามารถรับรู้ได้อย่างไร
- ภาษาประเภท 0 หรือที่เรียกว่าภาษานับซ้ำได้แตกต่างจากภาษาประเภทอื่นในแง่ของความซับซ้อนในการคำนวณอย่างไร
- อธิบายความแตกต่างระหว่างภาษาที่ไม่มีบริบทและภาษาที่คำนึงถึงบริบทในแง่ของกฎที่ควบคุมการก่อตัวของภาษาเหล่านั้น