الأوتومات غير المنتهي ذو المكدس

في علم الحاسوب، الأوتومات الدفع السفلي أو باختصار "PDA" هو نموذج حاسوبي بسيط يقوم على فكرة بنية البيانات المكدس (stack)، حيث أنه يستخدمه بأنه ذاكرة اضافية يُخزن فيها النتائج غير نهائية ليُعيد استخدامها لاحقا ضمن العمليات المُتاحة لهذا النموذج. هنالك نوعان من أوتوماتات الدفع السفلي: أوتومات الدفع السفلي القطعي (DPA)، أوتومات الدفع السفلي غير القطعي (PDA). على خلاف النماذج الابسط أوتومات الدفع السفلي غير القطعي «اقوى» من قرينه القطعي، أي يوجد لغات التي يمكن تقريرها بواسطة PDA ولكن ليس بواسطة DPA . أوتومات الدفع السفلي عمليا هو أوتومات حالات محدودة مُزود بمكدس LIFO أي من يدخل اخرا يخرج أولا، أول من أنتج الPDA's هو Anthony Oettinger في عام 1963 وقد كان المُكَّدس مستخدماً منذ زمن طويل، إلا أن أبحاثه نَظَّمت دمجه في أوتومات منتهي.ولعل أحد أهم المبرهنات في هذا المجال هي: لكل PDA يمكن بناء قواعد حرة السياق تنتج نفس اللغة. أهمية هذا الأوتومات تتبين من حقيقة انه يُستخدم كثيرا في عملية التجزئة (parsing) وخاصة انه أسهل للبرمجة من القواعد حرة السياق وقد تبين انهما ذوي قوة مضارعة.