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

في نظرية اللغات الرسمية ، تُعرَّف اللغة الحساسة للسياق بأنها لغة رسمية يمكن تعريفها بقواعد نحوية حساسة للسياق ، حيث يعتمد تطبيق قاعدة إنتاجية على السياق المحيط بالرموز. وعلى عكس القواعد النحوية غير الحساسة للسياق ، التي تُطبَّق قواعدها بغض النظر عن السياق، فإن القواعد النحوية الحساسة للسياق تسمح بتطبيق القواعد فقط عند وجود رموز متجاورة محددة، مما يُمكِّنها من التعبير عن التبعيات والتوافقات بين أجزاء متباعدة من سلسلة نصية.

تُطابق هذه اللغات لغات النوع الأول في تسلسل تشومسكي الهرمي ، وتُعرَّف بشكل مكافئ بقواعد نحوية غير مُختزلة (قواعد لا تُقلل فيها قواعد الإنتاج الطول الإجمالي للسلسلة). تستطيع اللغات الحساسة للسياق نمذجة ظواهر اللغة الطبيعية، مثل توافق الفاعل والفعل ، والتبعيات التسلسلية المتبادلة ، وغيرها من العلاقات النحوية المعقدة التي لا تستطيع أنواع القواعد النحوية الأبسط تمثيلها، مما يجعلها ذات أهمية بالغة في اللغويات الحاسوبية ومعالجة اللغة الطبيعية .

من الناحية الحسابية، تُعادل اللغة الحساسة للسياق آلة تورينغ غير حتمية محدودة خطيًا ، والتي تُسمى أيضًا آلة أوتوماتون محدودة خطيًا . أي أنها آلة تورينغ غير حتمية بشريط يحتوي فقط على${\displaystyle kn}$الخلايا، حيث${\displaystyle n}$حجم المدخلات و${\displaystyle k}$هو ثابت مرتبط بالآلة. وهذا يعني أن كل لغة رسمية يمكن أن تقررها هذه الآلة هي لغة حساسة للسياق، وكل لغة حساسة للسياق يمكن أن تقررها هذه الآلة.

تُعرف هذه المجموعة من اللغات أيضًا باسم NLINSPACE أو NSPACE( O ( n ))، نظرًا لإمكانية قبولها باستخدام مساحة خطية على آلة تورينغ غير حتمية. ^{[ 1 ]} تُعرَّف الفئة LINSPACE (أو DSPACE( O ( n ))) بنفس الطريقة، باستثناء استخدام آلة تورينغ حتمية . من الواضح أن LINSPACE هي مجموعة جزئية من NLINSPACE، ولكن ليس من المعروف ما إذا كانت LINSPACE = NLINSPACE. ^{[ 2 ]}

إحدى أبسط اللغات الحساسة للسياق ولكنها ليست خالية من السياق هي${\displaystyle L=\{a^{n}b^{n}c^{n}:n\geq 1\}}$لغة جميع السلاسل النصية التي تتكون من n تكرارًا للرمز "a"، ثم n تكرارًا للرمز "b"، ثم n تكرارًا للرمز "c" (مثل abc، aabbcc ، aaabbbccc ، إلخ). وتُعرَّف مجموعة فرعية من هذه اللغة، تُسمى لغة باخ، ^{[ 3 ]} بأنها مجموعة جميع السلاسل النصية التي يظهر فيها الرمز "a" والرمز "b" والرمز "c" (أو أي مجموعة أخرى من ثلاثة رموز) بنفس التواتر (مثل aabccb ، baabcaccb ، إلخ)، وهي أيضًا حساسة للسياق. ^{[ 4 ] [ 5 ]}

يمكن إثبات أن اللغة L حساسة للسياق من خلال بناء آلة خطية محدودة تقبل اللغة L. ويمكن بسهولة إثبات أن اللغة ليست منتظمة ولا خالية من السياق من خلال تطبيق معادلات الضخ الخاصة بكل فئة من فئات اللغة على اللغة L.

بصورة مماثلة:

${\displaystyle L_{\textit {Cross}}=\{a^{m}b^{n}c^{m}d^{n}:m\geq 1,n\geq 1\}}$هي لغة أخرى حساسة للسياق؛ ويمكن بسهولة إسقاط قواعدها النحوية الحساسة للسياق بدءًا من قاعدتين نحويتين خاليتين من السياق، تُنتجان صيغًا جملية بالصيغ التالية: ${\displaystyle a^{m}C^{m}}$ و ${\displaystyle B^{n}d^{n}}$ ثم استكمالها بإنتاج تباديل مثل ${\displaystyle CB\rightarrow BC}$، رمز بداية جديد وسكر نحوي قياسي.

${\displaystyle L_{MUL3}=\{a^{m}b^{n}c^{mn}:m\geq 1,n\geq 1\}}$هي لغة أخرى حساسة للسياق (يقصد الرقم "3" في اسم هذه اللغة أبجدية ثلاثية)؛ أي أن عملية "الضرب" تُعرّف لغة حساسة للسياق (لكن عملية "الجمع" تُعرّف لغة غير حساسة للسياق فقط، كما هو الحال في القواعد).${\displaystyle S\rightarrow aSc|R}$و${\displaystyle R\rightarrow bRc|bc}$(يُظهر). نظرًا لخاصية التبديل في الضرب، فإن القواعد النحوية الأكثر بديهية لـ${\displaystyle L_{\textit {MUL3}}}$هذا الأمر غامض. يمكن تجنب هذه المشكلة من خلال اعتماد تعريف أكثر تقييدًا للغة، على سبيل المثال${\displaystyle L_{\textit {ORDMUL3}}=\{a^{m}b^{n}c^{mn}:1<m<n\}}$يمكن تخصيص ذلك لـ ${\displaystyle L_{\textit {MUL1}}=\{a^{mn}:m>1,n>1\}}$ومن هذا، إلى${\displaystyle L_{m^{2}}=\{a^{m^{2}}:m>1\}}$،${\displaystyle L_{m^{3}}=\{a^{m^{3}}:m>1\}}$، إلخ.

${\displaystyle L_{REP}=\{w^{|w|}:w\in \Sigma ^{*}\}}$هي لغة حساسة للسياق. ويمكن الحصول على قواعدها النحوية الحساسة للسياق كتعميم لقواعد اللغة الحساسة للسياق الخاصة بـ${\displaystyle L_{\textit {Square}}=\{w^{2}:w\in \Sigma ^{*}\}}$،${\displaystyle L_{\textit {Cube}}=\{w^{3}:w\in \Sigma ^{*}\}}$، إلخ.

${\displaystyle L_{\textit {EXP}}=\{a^{2^{n}}:n\geq 1\}}$هي لغة حساسة للسياق. ^{[ 6 ]}

${\displaystyle L_{\textit {PRIMES2}}=\{w:|w|{\mbox{ is prime }}\}}$هي لغة حساسة للسياق (يشير الرقم "2" في اسم هذه اللغة إلى الأبجدية الثنائية). وقد أثبت هارتمانيس ذلك باستخدام مقولات الضخ للغات المنتظمة وغير الحساسة للسياق على الأبجدية الثنائية، وبعد ذلك، قام برسم مخطط لآلة متعددة الأشرطة محدودة خطيًا تقبل${\displaystyle L_{PRIMES2}}$[ ^{7 ]​}

${\displaystyle L_{\textit {PRIMES1}}=\{a^{p}:p{\mbox{ is prime }}\}}$هي لغة حساسة للسياق (يشير الرقم "1" في اسم هذه اللغة إلى أبجدية أحادية). وقد نسب أ. سالوما هذا الفضل إلى ماتي سويتولا من خلال آلة خطية محدودة على أبجدية أحادية ^{[ 8 ]} (الصفحات 213-214، التمرين 6.8)، وكذلك إلى مارتي بينتونين من خلال قواعد نحوية حساسة للسياق على أبجدية أحادية أيضًا (انظر: اللغات الرسمية لأ. سالوما، الصفحة 14، المثال 2.5).

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

• إن اتحاد وتقاطع ودمج لغتين حساسيتين للسياق هو أمر حساس للسياق، وكذلك عملية كلين بلس للغة حساسة للسياق. ^{[ 9 ]}
• إن مكمل اللغة الحساسة للسياق هو نفسه حساس للسياق ^{[ 10 ]} وهي نتيجة تُعرف باسم نظرية إيمرمان-سيليبسيني .
• إن انتماء سلسلة إلى لغة محددة بواسطة قواعد نحوية حساسة للسياق بشكل تعسفي، أو بواسطة قواعد نحوية حتمية حساسة للسياق بشكل تعسفي، هو مشكلة كاملة من نوع PSPACE .

• قائمة مولدات المحللات للغات الحساسة للسياق
• اللغات المفهرسة - مجموعة فرعية صارمة من اللغات الحساسة للسياق
• التسلسل الهرمي لـ Weir
• شكلية القواعد النحوية الحساسة للسياق بشكل طفيف - مجموعة من الشكليات لمختلف الفئات الفرعية للغات الحساسة للسياق

• Sipser, M. (1996), مقدمة في نظرية الحوسبة ، شركة PWS للنشر.