ماشین قطعی پشته ای

در نظریه اتوماتا یک اتومات های قطعی پشته ای ( Deterministic Pushdown Automaton ) یک نمونه از تمامی اتومات های پشته ای می باشد. ماشین اتومات های قطعی پشته ای زبان مستقل از متن قطعی را می پذیرد که زیرمجموعه ای از تمامی زبان های مستقل از متن است.
انتقال های ماشین براساس وضعیت موقعیت فعلی و نماد ورودی و نماد بر روی استک تعیین می شود و قابل ذکر است که نمادهای پایین تر در پشته قابل رویت نبوده و همچنین اثر فوری ندارند. اقدامات ماشین شامل حل دادن، ظاهر یا یا جایگزینی پشته بالا می باشد.
اتوماسیون پشته های قطعی حد اکثر یک انتقال قانونی برای همان ترکیب از نماد ورودی، حالت و نماد بالایی پشته می باشد. این همان نقطهٔ تفاوت ( اتوماسیون پشته های قطعی ) از پشته های غیر قطعی می باشد.
اگر ( L ( A یک زیان پذیرفته شده توسط ماشین پشته ای باشد A در صورتی می تواند توسط یک ماشین پشته ای قطعی پذیرفته شود اگر و تنها اگر یک محاسبات از پیکربندی اولیه انجام گیرد تا همهٔ رشته های متعلق به ( L ( A مورد پذیرش واقع شود.
اگر ( L ( A بتواند توسط یک ماشین پشته ای پذیرفته شود یک زبان مستقل از متن است و اگر بتواند توسط یک ماشین پشته ای قطعی پذیرفته شود یک گرامر مستقل از متن قطعی می باشد.
همهٔ زبان های مستقل از متن قطعی نخواهند بود. این موضوع ماشین پشته ای قطعی را بسیار ضعیف تر از ماشین پشته ای نشان می دهد.
برای مثال:
زبان مستقل از متن متقارن ( palindrome ) با طول زوج توسط ماشین پشته ای پذیرفته می شود اما توسط ماشین پشته ای قطعی پذیرفته نمی شود.
بستار زبان مستقل از متن قطعی کاملاً متفاوت از زبان مستقل از متن است.
به عنوان مثال آن ها تحت عمل مکمل بسته می باشد. اما تحت اجتماع بسته نمی باشد. اثبات این که زبان مستقل از متن قطعی تحت عمل مکمل بسته است سخت و دشوار می باشد.
نتیجه ای که مستوان از یک مکمل گرفت این است که یک زبان توسط ماشین قطعی پشته ای پذیرفته می شود اگر تمام رشته های داخل آن زبان توسط مکمل ماشین پشته ای قطعی آن زبان پذیرفته شود.
«گراد شینای ژروژ» ( Geraud Senizergues ) ثابت کرده است که هم ارزی ماشین پشته ای قطعی تصمیم پذیر می باشد؛ که این کار را او در سال ۲۰۰۲ انجام داد.