قواعد نحوية حساسة للسياق

لنرمز إلى القواعد النحوية الرسمية على النحو التالي:${\displaystyle G=(N,\Sigma ,P,S)}$، مع${\displaystyle N}$مجموعة من الرموز غير الطرفية،${\displaystyle \Sigma }$مجموعة من الرموز الطرفية،${\displaystyle P}$مجموعة من قواعد الإنتاج، و${\displaystyle S\in N}$رمز البداية.

خيط${\displaystyle u\in (N\cup \Sigma )^{*}}$ينتج عنه مباشرة ، أو يشتق منه مباشرة ، سلسلة نصية${\displaystyle v\in (N\cup \Sigma )^{*}}$، المشار إليه بـ${\displaystyle u\Rightarrow v}$إذا كان من الممكن الحصول على v من u بتطبيق قاعدة إنتاج معينة في P ، أي إذا${\displaystyle u=\gamma L\delta }$و${\displaystyle v=\gamma R\delta }$، أين${\displaystyle (L\to R)\in P}$هي قاعدة إنتاج، و${\displaystyle \gamma ,\delta \in (N\cup \Sigma )^{*}}$يمثل الجزء الأيسر والأيمن غير المتأثرين من السلسلة، على التوالي. وبشكل أعم، يُقال إن u ينتج عنه v ، أو يُشتق منه ، ويُرمز إليه بـ${\displaystyle u\Rightarrow ^{*}v}$إذا كان بالإمكان الحصول على v من u من خلال تطبيق قواعد الإنتاج بشكل متكرر، أي إذا${\displaystyle u=u_{0}\Rightarrow ...\Rightarrow u_{n}=v}$لبعض القيم n ≥ 0 وبعض السلاسل${\displaystyle u_{1},...,u_{n-1}\in (N\cup \Sigma )^{*}}$بمعنى آخر، العلاقة${\displaystyle \Rightarrow ^{*}}$هو الإغلاق الانعكاسي المتعدي للعلاقة${\displaystyle \Rightarrow }$.

لغة القواعد النحوية G هي مجموعة جميع سلاسل الرموز النهائية التي يمكن اشتقاقها من رمز البداية الخاص بها، بشكل رسمي :${\displaystyle L(G)=\{w\in \Sigma ^{*}\mid S\Rightarrow ^{*}w\}}$. الاشتقاقات التي لا تنتهي بسلسلة تتكون من رموز نهائية فقط ممكنة، ولكنها لا تساهم في L ( G ).

تكون القواعد النحوية الرسمية حساسة للسياق إذا كانت كل قاعدة في P إما من الشكل${\displaystyle S\to \varepsilon }$أين${\displaystyle \varepsilon }$هي سلسلة فارغة ، أو على شكل

α A β → αγβ

مع A ∈ N ، ^{[ ملاحظة 1 ]}${\displaystyle \alpha ,\beta \in (N\cup \Sigma \setminus \{S\})^{*}}$، ^{[ ملاحظة 2 ]} و${\displaystyle \gamma \in (N\cup \Sigma \setminus \{S\})^{+}}$[ ^{ملاحظة 3 ]}

يُفسَّر مصطلح "حساس للسياق" بالرمزين α و β اللذين يُشكِّلان سياق A ويُحدِّدان ما إذا كان يُمكن استبدال A بالرمز γ أم لا. في المقابل، في القواعد النحوية الخالية من السياق ، لا يوجد سياق: فالجانب الأيسر من كل قاعدة إنتاج هو مجرد رمز غير طرفي.

لا يُسمح بأن تكون السلسلة γ فارغة. وبدون هذا القيد، تصبح القواعد النحوية الناتجة مساوية في قوتها للقواعد النحوية غير المقيدة . ^{[ 10 ]}

القواعد غير المتقلصة هي قواعد يكون فيها طول u أقل من أو يساوي طول v لأي قاعدة إنتاج، من الشكل u → v .

كل قواعد اللغة الحساسة للسياق غير قابلة للانكماش، في حين يمكن تحويل كل قواعد اللغة غير القابلة للانكماش إلى قواعد لغة حساسة للسياق مكافئة؛ الفئتان متكافئتان بشكل ضعيف . ^{[ 12 ]}

يستخدم بعض المؤلفين مصطلح القواعد الحساسة للسياق للإشارة إلى القواعد غير المتقلصة بشكل عام.

تُعرَّف القواعد النحوية الحساسة للسياق الأيسر والقواعد النحوية الحساسة للسياق الأيمن بتقييد القواعد على الشكل α A → αγ و A β → γβ على التوالي. واللغات التي تولدها هذه القواعد النحوية هي أيضًا فئة كاملة من اللغات الحساسة للسياق. ^{[ 13 ]} وقد أُثبتت هذه المكافئة بواسطة الصيغة المعيارية لبنتونين . ^{[ 14 ]}

القواعد النحوية الحساسة للسياق التالية، مع رمز البداية S ، تولد اللغة غير الخالية من السياق المتعارف عليها { a ⁿ b ⁿ c ⁿ | n ≥ 1 }  :

تسمح القاعدتان 1 و2 بتوسيع S إلى n BC ( BC ) ^{n −1} ؛ وتسمح القواعد من 3 إلى 6 باستبدال كل CB بـ BC تباعًا ⁽ يلزم أربع قواعد لذلك لأن القاعدة CB → BC لا تتناسب مع المخطط α A β → αγβ)؛ وتسمح القواعد من 7 إلى 10 باستبدال B أو C غير الطرفي بنظيره الطرفي b أو c ، على التوالي، بشرط أن يكون في المكان الصحيح. سلسلة توليد aaabbbccc هي:

S

→ ₂ aSBC

→ ₂ a aSBC BC

→ ₁ aa aBC BCBC

→ ₃ aaaB CZ CBC

→ ₄ aaaB WZ CBC

→ ₅ aaaB WC CBC

→ ₆ aaaB BC CBC

→ ₃ aaaBBC CZ C

→ ₄ aaaBBC WZ C

→ ₅ aaaBBC WC C

→ ₆ aaaBBC BC C

→ ₃ aaaBB CZ CC

→ ₄ aaaBB WZ CC

→ ₅ aaaBB WC CC

→ ₆ aaaBB BC CC

→ ₇ aa ab BBCCC

→ ₈ aaa bb BCCC

→ ₈ aaab bb CCC

→ ₉ aaabb bc CC

→ ₁₀ aaabbb cc C

→ ₁₀ aaabbbc cc

يمكن استخدام قواعد نحوية أكثر تعقيدًا لتحليل { a ⁿ b ⁿ c ⁿ d ⁿ | n ≥ 1 }، ولغات أخرى تحتوي على عدد أكبر من الأحرف. هنا نعرض نهجًا أبسط باستخدام قواعد نحوية غير منكمشة: نبدأ بنواة من قواعد الإنتاج المنتظمة التي تولد الصيغ الجملية ${\displaystyle (ABCD)^{n}abcd}$ثم قم بتضمين الإنتاجات غير التعاقدية ${\displaystyle p_{Da}:Da\rightarrow aD}$، ${\displaystyle p_{Db}:Db\rightarrow bD}$، ${\displaystyle p_{Dc}:Dc\rightarrow cD}$، ${\displaystyle p_{Dd}:Dd\rightarrow dd}$، ${\displaystyle p_{Ca}:Ca\rightarrow aC}$، ${\displaystyle p_{Cb}:Cb\rightarrow bC}$، ${\displaystyle p_{Cc}:Cc\rightarrow cc}$، ${\displaystyle p_{Ba}:Ba\rightarrow aB}$، ${\displaystyle p_{Bb}:Bb\rightarrow bb}$، ${\displaystyle p_{Aa}:Aa\rightarrow aa}$.

قواعد نحوية غير متعاقدة (والتي يوجد لها قواعد نحوية متعاقدة مكافئة) للغة${\displaystyle L_{Cross}=\{a^{m}b^{n}c^{m}d^{n}\mid m\geq 1,n\geq 1\}}$يتم تعريفها بواسطة

${\displaystyle p_{0}:S\rightarrow RT}$،

${\displaystyle p_{1}:R\rightarrow aRC|aC}$،

${\displaystyle p_{3}:T\rightarrow BTd|Bd}$،

${\displaystyle p_{5}:CB\rightarrow BC}$،

${\displaystyle p_{6}:aB\rightarrow ab}$،

${\displaystyle p_{7}:bB\rightarrow bb}$،

${\displaystyle p_{8}:Cd\rightarrow cd}$، و

${\displaystyle p_{9}:Cc\rightarrow cc}$.

بناءً على هذه التعريفات، يمكن اشتقاق ما يلي:${\displaystyle a^{3}b^{2}c^{3}d^{2}}$يكون: ${\displaystyle S\Rightarrow _{p_{0}}RT\Rightarrow _{p_{1}^{2}p_{2}}a^{3}C^{3}T\Rightarrow _{p_{3}p_{4}}a^{3}C^{3}B^{2}d^{2}\Rightarrow _{p_{5}^{6}}a^{3}B^{2}C^{3}d^{2}\Rightarrow _{p_{6}p_{7}}a^{3}b^{2}C^{3}d^{2}\Rightarrow _{p_{8}p_{9}^{2}}a^{3}b^{2}c^{3}d^{2}}$.

تم إنشاء قواعد نحوية غير متقلصة للغة { a ^{2 i} | i ≥ 1 } في المثال 9.5 (ص  224) من (Hopcroft, Ullman, 1979): ^{[ 15 ]}

1. ${\displaystyle S\rightarrow [ACaB]}$
2. ${\displaystyle {\begin{cases}\ [Ca]a\rightarrow aa[Ca]\\\ [Ca][aB]\rightarrow aa[CaB]\\\ [ACa]a\rightarrow [Aa]a[Ca]\\\ [ACa][aB]\rightarrow [Aa]a[CaB]\\\ [ACaB]\rightarrow [Aa][aCB]\\\ [CaB]\rightarrow a[aCB]\end{cases}}}$
3. ${\displaystyle [aCB]\rightarrow [aDB]}$
4. ${\displaystyle [aCB]\rightarrow [aE]}$
5. ${\displaystyle {\begin{cases}\ a[Da]\rightarrow [Da]a\\\ [aDB]\rightarrow [DaB]\\\ [Aa][Da]\rightarrow [ADa]a\\\ a[DaB]\rightarrow [Da][aB]\\\ [Aa][DaB]\rightarrow [ADa][aB]\end{cases}}}$
6. ${\displaystyle [ADa]\rightarrow [ACa]}$
7. ${\displaystyle {\begin{cases}\ a[Ea]\rightarrow [Ea]a\\\ [aE]\rightarrow [Ea]\\\ [Aa][Ea]\rightarrow [AEa]a\end{cases}}}$
8. ${\displaystyle [AEa]\rightarrow a}$

يمكن وصف لغة رسمية بقواعد نحوية حساسة للسياق إذا وفقط إذا كانت مقبولة بواسطة آلة خطية محدودة (LBA). ^{[ 18 ]} في بعض الكتب الدراسية، تُنسب هذه النتيجة حصريًا إلى لاندويبر وكورودا . ^{[ 7 ]} بينما يسميها آخرون نظرية مايهيل -لاندويبر-كورودا. ^{[ 19 ]} (قدم مايهيل مفهوم الآلة الخطية المحدودة الحتمية عام 1960. ونشر بيتر س. لاندويبر عام 1963 أن اللغة المقبولة بواسطة آلة خطية محدودة حتمية هي لغة حساسة للسياق. ^{[ 20 ]} وقدم كورودا مفهوم الآلة الخطية المحدودة غير الحتمية والتكافؤ بين الآلات الخطية المحدودة والقواعد النحوية الحساسة للسياق عام 1964. ^{[ 21 ] [ 22 ]} )

اعتبارًا من عام 2010لا يزال السؤال مطروحاً حول ما إذا كان من الممكن قبول كل لغة حساسة للسياق بواسطة LBA حتمي . ^{[ 23 ]}

اللغات الحساسة للسياق مغلقة تحت عملية المكمل . تُعرف هذه النتيجة التي ظهرت عام 1988 باسم نظرية إيمرمان-سيليبسيني . ^{[ 19 ]} علاوة على ذلك، فهي مغلقة تحت عمليات الاتحاد ، والتقاطع ، والربط ، والاستبدال ، ^{[ ملاحظة 4 ]} والتشاكل العكسي ، ودالة كلين بلس . ^{[ 24 ]}

يمكن كتابة كل لغة قابلة للتعداد بشكل متكرر L على شكل h ( L ) لبعض اللغات الحساسة للسياق L وبعض التماثل السلسلي h . ^{[ 25 ]}

تُعدّ مسألة القرار التي تسأل عما إذا كانت سلسلة معينة s تنتمي إلى لغة قواعد نحوية حساسة للسياق G مسألة كاملة من فئة PSPACE . علاوة على ذلك، توجد قواعد نحوية حساسة للسياق لغاتها كاملة من فئة PSPACE. بعبارة أخرى، توجد قاعدة نحوية حساسة للسياق G بحيث يكون تحديد ما إذا كانت سلسلة معينة s تنتمي إلى لغة G مسألة كاملة من فئة PSPACE (أي أن G ثابتة، و s هي المدخل الوحيد للمسألة). ^{[ 26 ]}

تُعدّ مشكلة الفراغ بالنسبة للقواعد النحوية الحساسة للسياق (إذا كانت لدينا قاعدة نحوية حساسة للسياق G ، فهل L ( G ) = ∅  ؟) غير قابلة للتقرير . ^{[ 27 ] [ ملاحظة 5 ]}

أثبت سافيتش النتيجة النظرية التالية، التي يستند إليها في نقده لقواعد اللغة الحساسة للسياق كأساس للغة الطبيعية: لأي مجموعة قابلة للتعداد بشكل متكرر R ، توجد لغة/قواعد حساسة للسياق G يمكن استخدامها كنوع من الوكيل لاختبار العضوية في R بالطريقة التالية: بالنظر إلى سلسلة s ، فإن s تنتمي إلى R إذا وفقط إذا كان هناك عدد صحيح موجب n بحيث يكون sc ⁿ في G، حيث c ^هو رمز عشوائي ليس جزءًا من R. [ ^{10 ]}

لقد ثبت أن جميع اللغات الطبيعية تقريبًا يمكن وصفها عمومًا بقواعد نحوية حساسة للسياق، إلا أن فئة هذه القواعد تبدو أكبر بكثير من اللغات الطبيعية. والأسوأ من ذلك، أن مشكلة القرار المذكورة آنفًا لهذه القواعد هي مسألة كاملة من فئة PSPACE، مما يجعلها غير قابلة للتطبيق عمليًا، إذ أن خوارزمية ذات زمن متعدد الحدود لحل مسألة كاملة من فئة PSPACE تعني أن P=NP .

ثبت أن بعض اللغات الطبيعية ليست خالية من السياق، وذلك بناءً على تحديد ما يُسمى بالتبعيات التسلسلية المتبادلة وظواهر التشويش غير المحدود . مع ذلك، لا يعني هذا بالضرورة أن فئة قواعد السياق (CSGs) ضرورية لفهم "حساسية السياق" بالمعنى الدارج لهذه المصطلحات في اللغات الطبيعية. على سبيل المثال، تُعد أنظمة إعادة الكتابة الخطية الخالية من السياق (LCFRSs) أضعف من قواعد السياق، لكنها قادرة على تفسير ظاهرة التبعيات التسلسلية المتبادلة؛ إذ يُمكن كتابة قواعد LCFRSs للجمل { a ⁿ b ⁿ c ⁿ d ⁿ | n ≥ 1} على سبيل المثال. ^{[ 28 ] [ 29 ] [ 30 ]}

تركز الأبحاث الجارية في مجال اللغويات الحاسوبية على صياغة فئات أخرى من اللغات التي تتسم بـ" حساسية طفيفة للسياق " والتي تكون مسائل اتخاذ القرار فيها قابلة للحل، مثل قواعد الربط الشجري ، وقواعد التصنيف التوافقية ، واللغات الخالية من السياق المقترنة ، وأنظمة إعادة الكتابة الخطية الخالية من السياق . وتقع اللغات الناتجة عن هذه الصيغ الرسمية بين اللغات الخالية من السياق واللغات الحساسة للسياق.

في الآونة الأخيرة، تم ربط فئة PTIME بقواعد ربط النطاقات ، والتي تعتبر الآن الأكثر تعبيرًا بين فئات اللغات الحساسة للسياق المعتدل. ^{[ 30 ]}