ماشین قطعی پشته‌ای
در نظریه اتوماتا یک اتومات‌های قطعی پشته‌ای (Deterministic Pushdown Automaton) یک نمونه از تمامی اتومات های پشته‌ای می‌باشد. ماشین اتومات های قطعی پشته‌ای زبان مستقل از متن قطعی را می‌پذیرد که زیرمجموعه‌ای از تمامی زبان‌های مستقل از متن است.[۱]
انتقال‌های ماشین براساس وضعیت موقعیت فعلی و نماد ورودی و نماد بر روی استک تعیین می‌شود و قابل ذکر است که نمادهای پایین‌تر در پشته قابل رویت نبوده و همچنین اثر فوری ندارند. اقدامات ماشین شامل حل دادن، ظاهر یا یا جایگزینی پشته بالا می‌باشد.[۲]
اتوماسیون پشته‌های قطعی حد اکثر یک انتقال قانونی برای همان ترکیب از نماد ورودی، حالت و نماد بالایی پشته می‌باشد. این همان نقطهٔ تفاوت (اتوماسیون پشته‌های قطعی) از پشته‌های غیر قطعی می‌باشد.[۳]
زبان‌های شناخته شده
اگر (L(A یک زیان پذیرفته شده توسط ماشین پشته‌ای باشد A در صورتی می‌تواند توسط یک ماشین پشته‌ای قطعی پذیرفته شود اگر و تنها اگر یک محاسبات از پیکربندی اولیه انجام گیرد تا همهٔ رشته‌های متعلق به (L(A مورد پذیرش واقع شود.
اگر (L(A بتواند توسط یک ماشین پشته‌ای پذیرفته شود یک زبان مستقل از متن است و اگر بتواند توسط یک ماشین پشته‌ای قطعی پذیرفته شود یک گرامر مستقل از متن قطعی می‌باشد.
همهٔ زبان‌های مستقل از متن قطعی نخواهند بود. این موضوع ماشین پشته‌ای قطعی را بسیار ضعیف تر از ماشین پشته‌ای نشان می‌دهد.
برای مثال:
زبان مستقل از متن متقارن (palindrome) با طول زوج توسط ماشین پشته‌ای پذیرفته می‌شود اما توسط ماشین پشته‌ای قطعی پذیرفته نمی‌شود.
بستار
بستار زبان مستقل از متن قطعی کاملاً متفاوت از زبان مستقل از متن است.
به عنوان مثال آن‌ها تحت عمل مکمل بسته می‌باشد. اما تحت اجتماع بسته نمی‌باشد. اثبات این که زبان مستقل از متن قطعی تحت عمل مکمل بسته‌است سخت و دشوار می‌باشد.
نتیجه‌ای که مستوان از یک مکمل گرفت این است که یک زبان توسط ماشین قطعی پشته‌ای پذیرفته می‌شود اگر تمام رشته‌های داخل آن زبان توسط مکمل ماشین پشته‌ای قطعی آن زبان پذیرفته شود.
هم‌ارزی
«گراد شینای ژروژ» (Geraud Senizergues) ثابت کرده‌است که هم‌ارزی ماشین پشته‌ای قطعی تصمیم پذیر می‌باشد؛ که این کار را او در سال ۲۰۰۲ انجام داد.
منابع
- ↑ Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. p. 102. ISBN 0-534-94728-X.
- ↑ Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2006). Introduction to Automata Theory, Languages, and Computation (3rd ed.). Addison-Wesley. pp. 234, 254. ISBN 0-321-45536-3.
- ↑ Soltys-kulinicz, Michael (2018). An Introduction To The Analysis Of Algorithms (3rd ed.). World Scientific. pp. 193, 195. ISBN 9789813235922.