زبان مستقل‌ازمتن قطعی

مفهوم DCFL بسیار مرتبط با ماشین پشته‌ای قطعی (DPDA). می‌باشد. این جایی است که اگر آن را قطعی کنیم، قدرت زبان یک ماشین پشته‌ای کاهش می‌یابد؛ ماشین پشته‌ای در انتخاب بین گزینه‌های حالت گذار مختلف ناتوان می‌شود و در نتیجه نمی‌تواند همهٔ زبان‌های مستقل از متن را تشخیص دهد. گرامرهای واضح همیشه یک DCFL را تولید نمی‌کنند. به‌طور مثال، زبان پالیندرام با طول زوج در الفبای ۰ و ۱ می‌باشد، گرامر مستقل از متن S → 0S0 | 1S1 | ε را دارد. یک رشتهٔ اختیاری از این زبان، نمی‌تواند بدون خواندن تمام این حروف در ابتدا تجزیه شود، به این معنا که یک ماشین پشته‌ای باید حالت‌های گذار مختلف را برای جا دادن طول‌های ممکن مختلف از رشته‌های با تجزیهٔ مشابه، امتحان کند.

زبان‌های مستقل از متن قطعی می‌توانند با ماشین‌های تورینگ قطعی در یک زمان چند جمله‌ای و فضای O(log2 n)، تشخیص داده شود. به عنوان نتیجه، DCFL زیر مجموعه‌ای از کلاس پیچیدگی SC می‌باشد. مجموعهٔ زبانه‌ای مستقل از متن قطعی، نسبت به اجتماع بسته نیست ولی نسبت به تفاضل بسته است.

زبان‌های این گروه اهمیت کاربردی زیادی در علوم کامپیوتر دارند، از آنجا که آن‌ها می‌توانند به‌طور کاراتری نسبت به زبان‌های مستقل از متن غیر قطعی تجزیه شوند. پیچیدگی برنامه و زمان اجرای ماشین پشته‌ای قطعی به‌طور گسترده‌ای کمتر از حالت غیر قطعی است. در راه‌اندازی ساده دومی باید در هر زمان که یک مرحلهٔ غیر قطعی رخ می‌دهد، کپی‌هایی از پشته‌ها بسازد. بهترین الگوریتم شناخته شده برای آزمون عضویت در هر زبان مستقل از متن، الگوریتم ولینت می‌باشد که (O(n2.378 زمان می‌گیرد، که n طول رشته است. از طرف دیگر، زبان‌های مستقل از متن قطعی می‌توانند در زمان (O(n بوسیلهٔ تجزیه کنندهٔ (LR(k پذیرفته شوند. این برای ترجمه زبان برنامه نویسی بسیار مهم است زیرا بسیاری از زبان‌های کامپیوتری به این گروه از زبان‌ها تعلق دارند.

https://en.wikipedia.org/wiki/Deterministic_context-free_language