أوتومات الدفع السفلي
في علم الحاسوب ، الأوتومات الدفع السفلي أو باختصار "PDA" هو نموذج حاسوبي بسيط يقوم على فكرة بنية البيانات المكدس (stack) ، حيث أنه يستخدمه بأنه ذاكرة اضافية يُخزن فيها النتائج غير نهائية ليُعيد استخدامها لاحقا ضمن العمليات المُتاحة لهذا النموذج . هنالك نوعان من أوتوماتات الدفع السفلي : أوتومات الدفع السفلي القطعي (DPA) ، أوتومات الدفع السفلي غير القطعي (PDA) . على خلاف النماذج الابسط أوتومات الدفع السفلي غير القطعي "اقوى" من قرينه القطعي ، أي يوجد لغات التي يمكن تقريرها بواسطة PDA ولكن ليس بواسطة DPA . 
أوتومات الدفع السفلي عمليا هو أوتومات حالات محدودة مُزود بمكدس LIFO أي من يدخل اخرا يخرج أولا ، أول من أنتج الPDA's هو Anthony Oettinger في عام 1963 وقد كان المُكَّدس مستخدماً منذ زمن طويل ، إلا أن أبحاثه نَظَّمت دمجه في أوتومات منتهي .ولعل أحد أهم المبرهنات في هذا المجال هي : لكل PDA يمكن بناء قواعد حرة السياق تنتج نفس اللغة . أهمية هذا الأوتومات تتبين من حقيقة انه يُستخدم كثيرا في عملية التجزئة (parsing) وخاصة انه أسهل للبرمجة من القواعد حرة السياق وقد تبين انهما ذوي قوة مضارعة . 
أوتومات الدفع السفلي هو السباعية : formula_1 حيث يتحقق :
ملاحظات : 
صورة فورية(configuration) لأوتومات الدفع السفلي formula_25 مُكونة من حروف المُدخل التي لم يتم قراءتها بعد والحالة الحالية والمحتوى الحالي للمُكَّدس أي انه مجموعة الصور الفورية هي مجموعة جزئية ل-formula_26 .
دالة الانتقال formula_27 يمكننا بواسطتها تعريف علاقة الخطوة ، formula_28 ، والعلاقة مُعرفة على مجموعة الصور الفورية :
formula_29
من تبعيات هذا التعريف انَّ الأوتومات لا يمكنه المتابعة إذا ما فرغ المُكَدس لانه بكل خطوة عليه إخراج حرف أو رمز من المكدس .
حساب أوتومات ذو مكدس هو متتالية خطوات متلاحقة ، وعلاقة الحساب هي المنغلق الانعكاسي والمتعدي ،formula_30، لعلاقة الخطوة . 
PDA يقبل المدخل إذا حسابه على المُدخل بداية من الحالة الابتدائية مع وجود رمز المُكدس الابتدائي وتمام قراءة المُدخل واحد الامرين التاليين يتحقق :
بشكل عام هاتان اللغتان ، لأوتومات مُعين ، ليستا بالضرورة متساويان . لاحظ انه في الحالة الثانية لا يهم أية حالة وقفنا عليها (سواء كانت نهائية أو لا) .
بناء على ما تقدم سالفا نُعرف اللغتين بالشكل التالي :
فليكن formula_25 أوتومات دفع سفلي ، نعرف اللغتين التاليتين :
بشكل عام لا يتحقق التساوي بين اللغتين لكل أوتومات ، ولكن يمكن بناء أوتومات اخر بحيث يتحقق التساوي ، أي انه يتحقق التالي :
فليكن formula_36 أوتومات دفع سفلي حينها يمكننا بناء أوتومات formula_37 بحيث يتحقق : formula_38 . وكذا العكس . 
كل قواعد حر السياق الذي ينتج لغة يمكن تحويله بسهولة إلى أوتومات دفع سفلي يتعرف (recognize) على اللغة عينها . فليكن formula_39 نعرف الأوتومات التالي ذي الحالة الواحدة :formula_40 بحيث أنَّ formula_41 قوانينها كالتالي : 
حسابات formula_25 تقابل الاشتقاقات الأكثر يسارا (leftmost derivations) formula_47 ل- G ، رسميا : فليكن formula_48 وليكن formula_49 إذا formula_50 حينها يتحقق : formula_51 . كما أن العكس يتحقق لكل formula_52 .
حينما نأخذ formula_53 نجد أن : formula_54 فقط إذا formula_55 لكل formula_48 ، وهذا يعني أنَّ formula_57 ، هذا التوافق يُظهر أنَّ الأوتومات ذي الحالة الواحدة (حين الاخذ بالاعتبار لغة المُكدس الفارغ كما سبق تعريفها) مكافئ 
للقواعد 
حرة
السياق . التكافؤ لا يقف عند هذا الحد إذ أنَّ التكافؤ الكامل بين أوتومات الدفع السفلي وبين القواعد حرة السياق هو تكافؤ شامل وهذه النتيجة توصل إليها كل من نعوم تشومسكي ومارسيل-بوول شوتزنبرجر ، وإيفي . والمبرهنة تنص على أن كل لغة تُقبل بواسطة اتومات دفع سفلي سواء اكان ذلك بفراغ المُكدس ام بالوصول إلى حالة نهائية من مجموعة الحالات النهائية ، فقط إذا كانت هذه اللغة هي لغة حرة السياق .
فلتكن A , B لغتين اللتين تُمَيَّزَان (recognized) بواسطة اوتماتي الدفع السفلي formula_58 على التوالي .
1. الاتحاد : اللغة formula_59 يمكن أن تُمَيَّز بواسطة أوتومات دفع سفلي formula_60 . بحيث أن formula_60 مركب من الأوتوماتين formula_58 مع اضافة حالة جديدة وفي دالة العبور نضيف لهذه الحالة عبور بواسطة formula_63 ، كما هو مبين في الصورة . 
2. التسلسل : اللغة formula_64 يمكن أن تُمَيَّز بواسطة أوتومات دفع سفلي formula_65 . بحيث أن formula_65 مركب من الأوتوماتين formula_58 ، وفي دالة العبور نضيف عبور بواسطة formula_63 من مجموعة الحالات النهائية التي في A لبداية B .
3. فلتكن R لغة منظمة(regular language) حينها اللغة formula_69 يمكن تميزها بواسطة أوتومات دفع سفلي .
4. نجمة كليين : اللغة formula_70 يمكن أن تُمَيَّز بواسطة أوتومات دفع سفلي formula_71 . هذا يُبرهن بواسطة القواعد حرة السياق .
5. مورفزم عكسي : فليكن formula_72 مورفزم حينها اللغة : formula_73 يمكن أيضا ان تُميز بواسطة أوتومات دفع سفلي .
من وجهة نظر عملية أوتومات الدفع السفلي بصورته هذه لا يُعتبر مفيدا لتمييز اللغات أو حتى للتحليل النحوي (parsing) ، وذلك لانه ليس قطعيا أي انه في كل خطوة عليه ان يتحزر الصواب ويسلك طريقه . وخلافا لاتومات الحالات المنتهية فان أوتومات الدفع السفلي القطعي لا ينتج كل لغة حرة السياق أي انه ليس موديل لهذه اللغات كما هو الحال مع القواعد حرة السياق وكذا أوتومات الدفع السفلي غير القطعي . 
أوتومات الدفع السفلي formula_74 قطعي إذا تحقق التالي :
ملاحظة :
كما هو الحال مع الأوتومات الدفع السفلي الغير قطعي عندنا طريقتين لتعريف لغة الأوتومات : اما عن طريق الوصول إلى حالة نهائية مع انتهاء المُدخل أو بفراغ المُكدس مع انتهاء المُدخل . اما اللغات من الطريقة الثانية فهي لغات حرة البدايات (prefix free) أي : انَّ هذه اللغات لا تحوي الكلمة أو ايا من بدايتها في نفس الوقت . ولهذا السبب فإن هذه العائلة لا يمكن مقارنتها بعائلة اللغات المنتظمة (regular) .
وكما كان الحال مع اللغات حرة السياق وعلاقتها بأوتومات الدفع السفلي يمكن أيضا هنا في هذه الحالة قول نفس الشيء بالنسبة لعلاقة اللغات حرة البدايات مع الأوتومات القطعي . أي انه : لغة تُقبل بواسطة أوتومات دفع سفلي قطعي عن طريق فراغ المُكدس فقط إذا هي حرة السياق ويمكن أن تُقبل عن طريق أوتومات دفع سفلي قطعي (ربما اخر) عن طريق الوصول لحالة نهائية (وهذا يعني انه ليس كل لغة تُقبل عن الحالة النهائية يمكن أيضا أن تقبل عن طريق فراغ المُكدس لذا فالشرط أن اللغة حرة البدايات ضروري) . 
وهي مجموعة اللغات التي تُقبل بواسطة أوتومات دفع سفلي قطعي عن طريق الوصول لحالة نهائية . ولها يُرمز DCF . وهذه المجموعة تحوي مجموعة اللغات النظامية (regular languages) على أنها مجموعة جزئية فعلية أي formula_90 ، وهذا لان الأوتومات ذو الحالات النهائية القطعي يمكن النظر إليه على أنه أوتومات دفع سفلي قطعي يتجاهل المُكدس ، وكذلك يمكن بناء أوتومات دفع سفلي قطعي بسهولة للغة غير النظامية formula_91 . مجموعة اللغات حرة السياق(يُرمز لها CF) تحوي هذه المجموعة فعليا أي : formula_92 .