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

در نظریهٔ زبان صوری،زبان مستقل از متن قطعی (DCFL)، یک زیر مجموعهٔ سره از زبان‌های مستقل از متن می‌باشد. این زبانهای مستقل از متن هستند که می‌توانند بوسیلهٔ یک ماشین پشته‌ای قطعی پذیرفته شوند. DCFLها همیشه واضح هستند، به این معنی که آن‌ها یک گرامر واضح را می‌پذیرند، ولی هر. DCFL غیر تهی نیز یک گرامر مبهم را نیز می‌پذیرد. CFLهای واضح غیر قطعی نیز وجود دارند، بنابراین DCFLها یک زیر مجموعهٔ سره از CFLهای غیر مبهم را تشکیل می‌دهند. DCFLها علاقهٔ کاربردی زیادی دارند، آن طور که می‌توانند در زمان خطی تجزیه شوند و انواع محدود متنوع از DCFGها، تجزیه‌های کاربردی ساده‌ای را می‌پذیرند؛ بنابراین آن‌ها به‌طور گسترده‌ای در علوم کامپیوتر استفاده می‌شوند.

شرح

مفهوم 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