تدرج تشومسكي الهرمي
ينظم تدرج تشومسكي الهرمي اللغات الصورية في أربع فئات متداخلة، تُعرّف كل منها بتقييد على قواعد النحو وتُطابق نوعًا مميزًا من الآلات المجردة.
Definition
تدرج تشومسكي الهرمي هو تصنيف للنحو الصوري من خلال قيود أقوى تدريجيًا على قواعد إنتاجها، مما ينتج عنه فئات اللغات المنتظمة، والخالية من السياق، والحساسة للسياق، والقابلة للعد تكراريًا في سلسلة من التضمينات الصارمة.
Scope
يغطي هذا الموضوع الأنواع النحوية الأربعة — غير المقيدة، الحساسة للسياق، الخالية من السياق، والمنتظمة — واحتواءها الصارم، ونموذج الأتمتة المقابل لكل مستوى، وهي آلة تورينج، والأتمتة محدودة الخطية، والأتمتة الضاغطة، والأتمتة المحدودة، بالإضافة إلى خصائص الإغلاق والقابلية للتقرير التي تفصل المستويات.
Core questions
- كيف تترجم القيود على قواعد النحو إلى قيود على الذاكرة وقوة الحوسبة؟
- لماذا يحتوي كل مستوى من مستويات التدرج الهرمي المستوى الذي يليه بشكل صارم؟
- ما هو نموذج الأتمتة الذي يتوافق مع كل نوع نحوي؟
- كيف تتغير خصائص القابلية للتقرير والإغلاق كلما ارتفعنا في التدرج الهرمي؟
Key theories
- التوافق بين النحو والآلة
- يتم التعرف على كل فئة نحوية بواسطة نموذج آلة محدد — المنتظمة بواسطة الأتمتة المحدودة، والخالية من السياق بواسطة الأتمتة الضاغطة، والحساسة للسياق بواسطة الأتمتة محدودة الخطية، وغير المقيدة بواسطة آلات تورينج — مما يربط الأوصاف التوليدية والتشغيلية للحوسبة.
- التضمين الصارم لفئات اللغة
- يحتوي كل مستوى بشكل صحيح المستوى الذي يليه، ويشهد على ذلك لغات فصل ملموسة، لذا فإن التدرج الهرمي هو سلم حقيقي لقوة تعبيرية متزايدة بدلاً من مجموعة من الأوصاف المتكافئة.
Clinical relevance
التدرج الهرمي هو الخريطة التنظيمية لنظرية اللغة الصورية: فهو يخبر مصممي لغات البرمجة ولغات الاستعلام ومواصفات البروتوكولات بكمية الآليات التي تتطلبها فئة معينة من الأنماط، ويحدد الحدود بين ما هو قابل للتقرير وما هو قابل للتعرف عليه فقط.
History
اقترح تشومسكي التدرج الهرمي في أواخر الخمسينيات من القرن الماضي بينما كان يبحث عن نماذج صورية لبناء الجملة في اللغة الطبيعية، وتم تحديد التوافقات بين الآلات مع نضوج نظرية الأتمتة خلال الستينيات، مع تقديم مايهيل للأتمتة محدودة الخطية وتوضيح كورودا للمستوى الحساس للسياق.
Key figures
- Noam Chomsky
- Marcel-Paul Schützenberger
- John Myhill
Related topics
Seminal works
- hopcroft2006
- sipser2013
Frequently asked questions
- ما هي المستويات الأربعة لتدرج تشومسكي الهرمي؟
- من الأقل إلى الأكثر قوة هي اللغات المنتظمة (النوع 3)، واللغات الخالية من السياق (النوع 2)، واللغات الحساسة للسياق (النوع 1)، واللغات القابلة للعد تكراريًا (النوع 0). يخفف كل مستوى القيود على قواعد النحو ويتوافق مع آلة ذات ذاكرة أكبر.
- هل اللغة الطبيعية مشمولة بتدرج تشومسكي الهرمي؟
- كان التدرج الهرمي مدفوعًا في الأصل باللغويات، لكن معظم اللغويين يستنتجون أن اللغات الطبيعية ليست خالية من السياق، وتقع في مستوى غالبًا ما يسمى حساسًا للسياق بشكل معتدل. يظل التدرج الهرمي أساسيًا في علوم الكمبيوتر على الرغم من أن اللغة البشرية تتناسب معه بشكل فضفاض فقط.