أوتومات الدفع السفلي

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

صورة فورية

صورة فورية(configuration) لأوتومات الدفع السفلي  مُكونة من حروف المُدخل التي لم يتم قراءتها بعد والحالة الحالية والمحتوى الحالي للمُكَّدس أي انه مجموعة الصور الفورية هي مجموعة جزئية ل- .

علاقة الخطوة

دالة الانتقال  يمكننا بواسطتها تعريف علاقة الخطوة ،  ، والعلاقة مُعرفة على مجموعة الصور الفورية :
من تبعيات هذا التعريف انَّ الأوتومات لا يمكنه المتابعة إذا ما فرغ المُكَدس لانه بكل خطوة عليه إخراج حرف أو رمز من المكدس .

حساب

حساب أوتومات ذو مكدس هو متتالية خطوات متلاحقة ، وعلاقة الحساب هي المنغلق الانعكاسي والمتعدي ،، لعلاقة الخطوة .

صفات انغلاق

فلتكن A , B لغتين اللتين تُمَيَّزَان (recognized) بواسطة اوتماتي الدفع السفلي  على التوالي .
1. الاتحاد : اللغة  يمكن أن تُمَيَّز بواسطة أوتومات دفع سفلي  . بحيث أن   مركب من الأوتوماتين  مع اضافة حالة جديدة وفي دالة العبور نضيف لهذه الحالة عبور بواسطة  ، كما هو مبين في الصورة . 
2. التسلسل : اللغة  يمكن أن تُمَيَّز بواسطة أوتومات دفع سفلي  . بحيث أن   مركب من الأوتوماتين  ، وفي دالة العبور نضيف عبور بواسطة  من مجموعة الحالات النهائية التي في  A لبداية B .
3. فلتكن R لغة منظمة(regular language) حينها اللغة  يمكن تميزها بواسطة أوتومات دفع سفلي .
4. نجمة كليين : اللغة  يمكن أن تُمَيَّز بواسطة أوتومات دفع سفلي  . هذا يُبرهن بواسطة القواعد حرة السياق .
5. مورفزم عكسي : فليكن  مورفزم حينها اللغة :  يمكن أيضا ان تُميز بواسطة أوتومات دفع سفلي .

أوتومات دفع سفلي قطعي

من وجهة نظر عملية أوتومات الدفع السفلي بصورته هذه لا يُعتبر مفيدا لتمييز اللغات أو حتى للتحليل النحوي (parsing) ، وذلك لانه ليس قطعيا أي انه في كل خطوة عليه ان يتحزر الصواب ويسلك طريقه . وخلافا لاتومات الحالات المنتهية فان أوتومات الدفع السفلي القطعي لا ينتج كل لغة حرة السياق أي انه ليس موديل لهذه اللغات كما هو الحال مع القواعد حرة السياق وكذا أوتومات الدفع السفلي غير القطعي .

لغات الأوتومات القطعي

كما هو الحال مع الأوتومات الدفع السفلي الغير قطعي عندنا طريقتين لتعريف لغة الأوتومات : اما عن طريق الوصول إلى حالة نهائية مع انتهاء المُدخل أو بفراغ المُكدس مع انتهاء المُدخل . اما اللغات من الطريقة الثانية فهي لغات حرة البدايات (prefix free) أي : انَّ هذه اللغات لا تحوي الكلمة أو ايا من بدايتها في نفس الوقت . ولهذا السبب فإن هذه العائلة لا يمكن مقارنتها بعائلة اللغات المنتظمة (regular) .
وكما كان الحال مع اللغات حرة السياق وعلاقتها بأوتومات الدفع السفلي يمكن أيضا هنا في هذه الحالة قول نفس الشيء بالنسبة لعلاقة اللغات حرة البدايات  مع الأوتومات القطعي . أي انه : لغة تُقبل بواسطة أوتومات دفع سفلي قطعي عن طريق فراغ المُكدس فقط إذا هي حرة السياق ويمكن أن تُقبل عن طريق أوتومات دفع سفلي قطعي (ربما اخر) عن طريق الوصول لحالة نهائية (وهذا يعني انه ليس كل لغة تُقبل عن الحالة النهائية يمكن أيضا أن تقبل عن طريق فراغ المُكدس لذا فالشرط أن اللغة حرة البدايات ضروري) .

قواعد حرة السياق قطعية

وهي مجموعة اللغات التي تُقبل بواسطة أوتومات دفع سفلي قطعي عن طريق الوصول لحالة نهائية . ولها يُرمز DCF . وهذه المجموعة تحوي مجموعة اللغات النظامية (regular languages) على أنها مجموعة جزئية فعلية أي  ، وهذا لان الأوتومات ذو الحالات النهائية القطعي يمكن النظر إليه على أنه أوتومات دفع سفلي قطعي يتجاهل المُكدس ، وكذلك يمكن بناء أوتومات دفع سفلي قطعي بسهولة للغة غير النظامية  . مجموعة اللغات حرة السياق(يُرمز لها CF) تحوي هذه المجموعة فعليا أي :   .