
_START_ARTICLE_
أوتومات الدفع السفلي
_START_PARAGRAPH_
في علم الحاسوب ، الأوتومات الدفع السفلي أو باختصار "PDA" هو نموذج حاسوبي بسيط يقوم على فكرة بنية البيانات المكدس (stack) ، حيث أنه يستخدمه بأنه ذاكرة اضافية يُخزن فيها النتائج غير نهائية ليُعيد استخدامها لاحقا ضمن العمليات المُتاحة لهذا النموذج . هنالك نوعان من أوتوماتات الدفع السفلي : أوتومات الدفع السفلي القطعي (DPA) ، أوتومات  الدفع السفلي غير القطعي (PDA) . على خلاف النماذج الابسط أوتومات الدفع السفلي غير القطعي "اقوى" من قرينه القطعي ، أي يوجد لغات التي يمكن تقريرها بواسطة PDA ولكن ليس بواسطة DPA . _NEWLINE_أوتومات الدفع السفلي عمليا هو أوتومات حالات محدودة مُزود بمكدس LIFO أي من يدخل اخرا يخرج أولا ، أول من أنتج الPDA's هو Anthony Oettinger في عام 1963 وقد كان المُكَّدس مستخدماً منذ زمن طويل ، إلا أن أبحاثه نَظَّمت دمجه في أوتومات منتهي .ولعل أحد أهم المبرهنات في هذا المجال هي : لكل PDA يمكن بناء قواعد حرة السياق تنتج نفس اللغة . أهمية هذا الأوتومات تتبين من حقيقة انه يُستخدم كثيرا في عملية التجزئة (parsing) وخاصة انه أسهل للبرمجة من القواعد حرة السياق وقد تبين انهما ذوي قوة مضارعة .
_START_SECTION_
صورة فورية
_START_PARAGRAPH_
صورة فورية(configuration) لأوتومات الدفع السفلي  مُكونة من حروف المُدخل التي لم يتم قراءتها بعد والحالة الحالية والمحتوى الحالي للمُكَّدس أي انه مجموعة الصور الفورية هي مجموعة جزئية ل- .
_START_SECTION_
علاقة الخطوة
_START_PARAGRAPH_
دالة الانتقال  يمكننا بواسطتها تعريف علاقة الخطوة ،  ، والعلاقة مُعرفة على مجموعة الصور الفورية :_NEWLINE_من تبعيات هذا التعريف انَّ الأوتومات لا يمكنه المتابعة إذا ما فرغ المُكَدس لانه بكل خطوة عليه إخراج حرف أو رمز من المكدس .
_START_SECTION_
حساب
_START_PARAGRAPH_
حساب أوتومات ذو مكدس هو متتالية خطوات متلاحقة ، وعلاقة الحساب هي المنغلق الانعكاسي والمتعدي ،، لعلاقة الخطوة .
_START_SECTION_
صفات انغلاق
_START_PARAGRAPH_
فلتكن A , B لغتين اللتين تُمَيَّزَان (recognized) بواسطة اوتماتي الدفع السفلي  على التوالي ._NEWLINE_1. الاتحاد : اللغة  يمكن أن تُمَيَّز بواسطة أوتومات دفع سفلي  . بحيث أن   مركب من الأوتوماتين  مع اضافة حالة جديدة وفي دالة العبور نضيف لهذه الحالة عبور بواسطة  ، كما هو مبين في الصورة . _NEWLINE_2. التسلسل : اللغة  يمكن أن تُمَيَّز بواسطة أوتومات دفع سفلي  . بحيث أن   مركب من الأوتوماتين  ، وفي دالة العبور نضيف عبور بواسطة  من مجموعة الحالات النهائية التي في  A لبداية B ._NEWLINE_3. فلتكن R لغة منظمة(regular language) حينها اللغة  يمكن تميزها بواسطة أوتومات دفع سفلي ._NEWLINE_4. نجمة كليين : اللغة  يمكن أن تُمَيَّز بواسطة أوتومات دفع سفلي  . هذا يُبرهن بواسطة القواعد حرة السياق ._NEWLINE_5. مورفزم عكسي : فليكن  مورفزم حينها اللغة :  يمكن أيضا ان تُميز بواسطة أوتومات دفع سفلي .
_START_SECTION_
أوتومات دفع سفلي قطعي
_START_PARAGRAPH_
من وجهة نظر عملية أوتومات الدفع السفلي بصورته هذه لا يُعتبر مفيدا لتمييز اللغات أو حتى للتحليل النحوي (parsing) ، وذلك لانه ليس قطعيا أي انه في كل خطوة عليه ان يتحزر الصواب ويسلك طريقه . وخلافا لاتومات الحالات المنتهية فان أوتومات الدفع السفلي القطعي لا ينتج كل لغة حرة السياق أي انه ليس موديل لهذه اللغات كما هو الحال مع القواعد حرة السياق وكذا أوتومات الدفع السفلي غير القطعي .
_START_SECTION_
لغات الأوتومات القطعي
_START_PARAGRAPH_
كما هو الحال مع الأوتومات الدفع السفلي الغير قطعي عندنا طريقتين لتعريف لغة الأوتومات : اما عن طريق الوصول إلى حالة نهائية مع انتهاء المُدخل أو بفراغ المُكدس مع انتهاء المُدخل . اما اللغات من الطريقة الثانية فهي لغات حرة البدايات (prefix free) أي : انَّ هذه اللغات لا تحوي الكلمة أو ايا من بدايتها في نفس الوقت . ولهذا السبب فإن هذه العائلة لا يمكن مقارنتها بعائلة اللغات المنتظمة (regular) ._NEWLINE_وكما كان الحال مع اللغات حرة السياق وعلاقتها بأوتومات الدفع السفلي يمكن أيضا هنا في هذه الحالة قول نفس الشيء بالنسبة لعلاقة اللغات حرة البدايات  مع الأوتومات القطعي . أي انه : لغة تُقبل بواسطة أوتومات دفع سفلي قطعي عن طريق فراغ المُكدس فقط إذا هي حرة السياق ويمكن أن تُقبل عن طريق أوتومات دفع سفلي قطعي (ربما اخر) عن طريق الوصول لحالة نهائية (وهذا يعني انه ليس كل لغة تُقبل عن الحالة النهائية يمكن أيضا أن تقبل عن طريق فراغ المُكدس لذا فالشرط أن اللغة حرة البدايات ضروري) .
_START_SECTION_
قواعد حرة السياق قطعية
_START_PARAGRAPH_
وهي مجموعة اللغات التي تُقبل بواسطة أوتومات دفع سفلي قطعي عن طريق الوصول لحالة نهائية . ولها يُرمز DCF . وهذه المجموعة تحوي مجموعة اللغات النظامية (regular languages) على أنها مجموعة جزئية فعلية أي  ، وهذا لان الأوتومات ذو الحالات النهائية القطعي يمكن النظر إليه على أنه أوتومات دفع سفلي قطعي يتجاهل المُكدس ، وكذلك يمكن بناء أوتومات دفع سفلي قطعي بسهولة للغة غير النظامية  . مجموعة اللغات حرة السياق(يُرمز لها CF) تحوي هذه المجموعة فعليا أي :   .