لغة حساسة للسياق

في علم الحاسوب النظري، عبارة «لغة حساسة للسياق» تعني لغة رسمية يمكن تعريفها كنحو حساس للسياق. هذا أحد أنواع النحو الأربعة في تسلسل شومسكي. من بين الأربعة، هذه هي الأقل استخداما، في الجانبين النظري والعملي.

الخواص الحسابية

حسابيا، اللغة الحساسة للسياق تكافئ آلة تورنغ غير حتمية محدودة خطيا، وتسمى أيضا تشغل آلي محدود خطيا. وهي آلة تورنغ غير حتمية بشريط يتكون من خلايا "kn"، حيث “n هي حجم المدخل و"k" ثابت مرتبط بالآلة. هذا يعني أن كل لغة رسمية يمكن وصفها من قبل آلة كتلك ستكون لغة حساسة للسياق، وكل لغة حساسة للسياق يمكن وصفها من قبل آلة كتلك.

هذه المجموعة من اللغات تعرف أيضا باسم NLIN-SPACE، لأنها يمكن أن تُقبل بواسطة فضاء خطي في آلة تورنغ غير حتمية. الفئة LIN-SPACE تعرّف بنفس الطريقة، ما عدا استخدام آلة تورنغ حتمية. بشكل واضح فإن LIN-SPACE هو مجموعة فرعية من NLIN-SPACE، لكنه من غير المعروف ما إذا كان LIN-SPACE=NLIN-SPACE. هناك توقع شائع أنهما غير متساويتان.

أمثلة

مثال على لغة حساسة للسياق لكنها ليست حرة السياق هو L = { a^p : p is a prime number }. يمكن إثبات أن L لغة حساسة للسياق بإنشاء تشغيل آلي محدود خطيا يقبل L. يمكن بسهولة إثبات أن اللغة ليست لغة عادية ولا لغة خالية من السياق بتطبيق جدل الضخ (pumping lemm) المناسب لكل فئة لغة على L.

مثال على اللغة الاسترجاعية والتي ليست حساسة للسياق هو أي لغة استرجاعية والتي قرارها يقع ضمن مشكلة صعبة من فئة EXPSPACE-، مثلا مجموعة أزواج الالتعبيرات العادية مع الأساس.

خواص اللغات الحساسة للسياق

الاتحاد، التقاطع والتسلسل للغتين حساستين للسياق يكون حساسا للسياق.
المكمل للغة حساسة للسياق هو بنفسه حساس للسياق.
كل لغة ذات نحو خال من السياق تكون حساسة للسياق.

عضوية عبارة في لغة معرّفة بنحوعشوائي حساس للسياق، أو بنحو عشوائي حتمي حساس للسياق، هو مشكلة من فئة مسائل PSPACE كاملة.

المراجع

Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.
Immerman، Neil (1988). "Nondeterministic space is closed under complementation". SIAM J. Comput. ج. 17 ع. 5: 935–938. DOI:10.1137/0217058. {{استشهاد بدورية محكمة}}: روابط خارجية في |عنوان= (مساعدة)