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

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

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

يرتبط مفهوم اللغة الخالية من السياق (DCFL) ارتباطًا وثيقًا بآلة الدفع الحتمية (DPDA). وتتمثل هذه اللغة في انخفاض قدرة آلات الدفع على اللغة إلى أدنى حد عند جعلها حتمية؛ إذ تصبح هذه الآلات عاجزة عن الاختيار بين بدائل انتقال الحالة المختلفة، وبالتالي لا يمكنها التعرف على جميع اللغات الخالية من السياق. ^{[ 1 ]} لا تُنتج القواعد النحوية غير المبهمة دائمًا لغة خالية من السياق. على سبيل المثال، لغة المتناظرات ذات الطول الزوجي على أبجدية 0 و1 لها قاعدة نحوية خالية من السياق غير مبهمة S → 0S0 | 1S1 | ε. لا يمكن تحليل أي سلسلة نصية من هذه اللغة دون قراءة جميع حروفها أولًا، مما يعني أن على آلة الدفع تجربة انتقالات حالة بديلة لاستيعاب الأطوال المختلفة الممكنة لسلسلة نصية شبه مُحللة. ^{[ 2 ]}

يمكن التعرف على اللغات الخالية من السياق الحتمية بواسطة آلة تورينج حتمية في وقت متعدد الحدود ومساحة O (log ² n ) ؛ وكنتيجة لذلك، فإن DCFL هي مجموعة فرعية من فئة التعقيد SC . ^{[ 3 ]}

تُغلق مجموعة اللغات الحتمية الخالية من السياق تحت العمليات التالية: ^{[ 4 ]}

• إطراء
• التماثل العكسي
• القسمة اليمنى مع لغة منتظمة
• pre: pre(${\displaystyle L}$) هي مجموعة فرعية من جميع السلاسل التي تحتوي على بادئة مناسبة تنتمي أيضًا إلى${\displaystyle L}$.
• الحد الأدنى: الحد الأدنى(${\displaystyle L}$) هي مجموعة فرعية من جميع السلاسل التي لا تحتوي على بادئة مناسبة في${\displaystyle L}$.
• الحد الأقصى: الحد الأقصى(${\displaystyle L}$) هي مجموعة فرعية من جميع السلاسل التي لا تُشكّل بادئة لسلسلة أطول في${\displaystyle L}$.

مجموعة اللغة الخالية من السياق الحتمية ليست مغلقة في ظل العمليات التالية: ^{[ 4 ]}

• الاتحاد
• تقاطع
• سلسلة
• كلين ستار
• التشكل الخالي من إبسيلون
• صورة معكوسة

تتمتع لغات هذه الفئة بأهمية عملية كبيرة في علوم الحاسوب، إذ يمكن تحليلها بكفاءة أعلى بكثير من لغات السياق غير الحتمية. يُعد تعقيد البرنامج ووقت تنفيذ آلة الدفع الحتمية أقل بكثير من نظيرتها غير الحتمية. في التنفيذ البسيط، يجب على الأخيرة إنشاء نسخ من المكدس في كل مرة تحدث فيها خطوة غير حتمية. أفضل خوارزمية معروفة لاختبار الانتماء إلى أي لغة سياقية هي خوارزمية فاليانت ، التي تستغرق زمنًا قدره O( n² ^{, 378} )، حيث n هو طول السلسلة. من ناحية أخرى، يمكن قبول لغات السياق الحتمية في زمن قدره O( n ) بواسطة محلل LR( k ) . ^{[ 5 ]} هذا مهم جدًا لترجمة لغات الحاسوب، لأن العديد من لغات الحاسوب تنتمي إلى هذه الفئة من اللغات.

• لغة خالية من السياق
• آلة دفع حتمية
• قواعد نحوية حتمية خالية من السياق
• لغة حتمية بسيطة