مرجع
آخر الزيارات

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

306 كلمة•0 مشاهدة•🗒️ منذ يوم
باختصار: في علم الحاسوب النظري، عبارة «لغة حساسة للسياق» تعني لغة رسمية يمكن تعريفها كنحو حساس للسياق. في هذه المقالة 3 أقسام: «الخواص الحسابية»، «خواص اللغات الحساسة للسياق» و«أمثلة».
المحتويات
  1. الخواص الحسابية
  2. خواص اللغات الحساسة للسياق
  3. أمثلة

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

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

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

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

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

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

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

أمثلة

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

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

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.