لغة خالية من السياق

يمكن لقواعد نحوية مختلفة خالية من السياق أن تُنتج نفس اللغة الخالية من السياق. ويمكن التمييز بين الخصائص الجوهرية للغة والخصائص الخارجية لقاعدة نحوية معينة من خلال مقارنة قواعد نحوية متعددة تصف تلك اللغة.

مجموعة جميع اللغات الخالية من السياق مطابقة لمجموعة اللغات التي تقبلها آلات الدفع السفلي ، مما يجعل هذه اللغات قابلة للتحليل النحوي. علاوة على ذلك، بالنسبة لقواعد نحوية خالية من السياق معينة، توجد طريقة مباشرة لإنتاج آلة دفع سفلي لتلك القواعد (وبالتالي اللغة المقابلة لها)، على الرغم من أن الاتجاه المعاكس (إنتاج قواعد نحوية انطلاقًا من آلة دفع سفلي) ليس بهذه المباشرة.

يتم توليد لغة جميع الأقواس المتطابقة بشكل صحيح بواسطة القواعد النحوية${\displaystyle S\to SS~|~(S)~|~\varepsilon }$.

إن الطبيعة الخالية من السياق للغة تجعل من السهل تحليلها باستخدام آلة الدفع لأسفل.

تحديد حالة من حالات مشكلة الانتماء ؛ أي بالنظر إلى سلسلة نصية${\displaystyle w}$، تحديد ما إذا${\displaystyle w\in L(G)}$أين${\displaystyle L}$هي اللغة التي تولدها قواعد نحوية معينة${\displaystyle G}$يُعرف أيضًا باسم التعرف . وقد أثبت ليزلي جي. فاليانت أن التعرف الخالي من السياق لقواعد تشومسكي النحوية العادية قابل للاختزال إلى ضرب المصفوفات المنطقية ، وبالتالي يرث حده الأعلى للتعقيد O ( n².3728596 ). ^{[ 2 ] [ ملاحظة 2 ]} في المقابل، أثبتت ليليان لي أن ضرب المصفوفات المنطقية O ( n³ ^{- ε} ) قابل للاختزال إلى تحليل قواعد اللغة الخالية ^{من السياق} O ( n³ ^{- 3ε} )، وبالتالي تحديد حد أدنى لهذا الأخير. ^{[ 3 ]}

تتطلب الاستخدامات العملية للغات الخالية من السياق أيضًا إنتاج شجرة اشتقاق تُظهر البنية التي تربطها القواعد النحوية بالسلسلة النصية المُعطاة. تُسمى عملية إنتاج هذه الشجرة بالتحليل النحوي . تتميز المحللات النحوية المعروفة بتعقيد زمني يتناسب طرديًا مع مكعب حجم السلسلة النصية التي يتم تحليلها.

بصورة رسمية، فإن مجموعة جميع اللغات الخالية من السياق هي نفسها مجموعة اللغات التي تقبلها آلات الدفع لأسفل (PDA). تشمل خوارزميات التحليل اللغوي للغات الخالية من السياق خوارزمية CYK وخوارزمية إيرلي .

تُعتبر اللغات الخالية من السياق الحتمية فئة فرعية خاصة من اللغات الخالية من السياق ، وهي تُعرف بأنها مجموعة اللغات التي يقبلها جهاز دفع حتمي ويمكن تحليلها بواسطة محلل LR(k) . ^{[ 4 ]}

انظر أيضًا إلى تحليل قواعد التعبير كنهج بديل للقواعد النحوية والمحلل النحوي.

تُعتبر فئة اللغات الخالية من السياق مغلقةً تحت العمليات التالية. أي، إذا كانت اللغتان L و P خاليتين من السياق، فإن اللغات التالية خالية من السياق أيضاً:

• الاتحاد​${\displaystyle L\cup P}$من L و P ^{[ 5 ]}
• انعكاس L ^{[ 6 ]}
• التسلسل​${\displaystyle L\cdot P}$من L و P ^{[ 5 ]}
• نجم كلين${\displaystyle L^{*}}$من L ^{[ 5 ]}
• الصورة${\displaystyle \varphi (L)}$لـ L تحت التشاكل${\displaystyle \varphi }$^{[ 7 ]}
• الصورة${\displaystyle \varphi ^{-1}(L)}$لـ L تحت التشاكل العكسي${\displaystyle \varphi ^{-1}}$^{[ 8 ]}
• التحول الدائري للغة L​${\displaystyle \{vu:uv\in L\}}$) ^{[ 9 ]}
• الإغلاق البادئ لـ L (مجموعة جميع البادئات للسلاسل من L ) ^{[ 10 ]}
• حاصل قسمة L / R لـ L على لغة منتظمة R ^{[ 11 ]}

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

المسائل التالية غير قابلة للحل بالنسبة لقواعد اللغة الخالية من السياق المعطاة بشكل تعسفي A و B:

• التكافؤ: هو${\displaystyle L(A)=L(B)}$؟ ^{[ 14 ]}
• الانفصال: هو${\displaystyle L(A)\cap L(B)=\emptyset }$ ? ^{[ 15 ]} ومع ذلك، فإن تقاطع لغة خالية من السياق ولغة منتظمة هو لغة خالية من السياق، ^{[ 16 ] [ 17 ]} وبالتالي فإن متغير المشكلة حيث B هي قواعد منتظمة قابل للتقرير (انظر "الفراغ" أدناه).
• الاحتواء: هو${\displaystyle L(A)\subseteq L(B)}$ [ ^{18 ]} مرة أخرى، يمكن حل صيغة المشكلة التي تكون فيها B قواعد منتظمة، بينما لا يمكن حل الصيغة التي تكون فيها A قواعد منتظمة ^بشكل عام . ^{[ 19 ]}
• العالمية: هي${\displaystyle L(A)=\Sigma ^{*}}$؟ ^{[ 20 ]}
• الانتظام: هو${\displaystyle L(A)}$لغة منتظمة؟ ^{[ 21 ]}
• الغموض: هل كل قواعد اللغة لـ${\displaystyle L(A)}$غامض؟ ^{[ 22 ]}

يمكن حل المشكلات التالية للغات الخالية من السياق بشكل عشوائي:

• الفراغ: بالنظر إلى قواعد نحوية خالية من السياق A ، يكون${\displaystyle L(A)=\emptyset }$ ؟ ^{[ 23 ]}
• التناهي: بالنظر إلى قواعد نحوية خالية من السياق A ، هل${\displaystyle L(A)}$محدود؟ ^{[ 24 ]}
• العضوية: بالنظر إلى قواعد نحوية خالية من السياق G ، وكلمة${\displaystyle w}$، يفعل${\displaystyle w\in L(G)}$ تُعد خوارزمية CYK وخوارزمية إيرلي من الخوارزميات الفعالة ذات الوقت متعدد الحدود لحل مشكلة العضوية .

وفقًا لهوبكروفت ، وموتواني ، وأولمان (2006)، ^{[ 25 ]} فقد تم عرض العديد من خصائص الإغلاق الأساسية وعدم قابلية الحسم للغات الخالية من السياق في ورقة بار-هيلل ، وبيرلز، وشامير عام 1961. ^{[ 26 ]}

المجموعة${\displaystyle \{a^{n}b^{n}c^{n}d^{n}|n>0\}}$هي لغة حساسة للسياق ، ولكن لا توجد قواعد نحوية خالية من السياق تولد هذه اللغة. ^{[ 27 ]} لذا، توجد لغات حساسة للسياق ليست خالية من السياق. لإثبات أن لغة معينة ليست خالية من السياق، يمكن استخدام مبرهنة الضخ للغات الخالية من السياق ^{[ 26 ]} أو عدد من الطرق الأخرى، مثل مبرهنة أوجدن أو نظرية باريك . ^{[ 28 ]}