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

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

المراجع

areq.net

التصانيف

معلوماتية نظرية  نظرية الأوتومات  نظرية التعقيد  بنية الحاسب   العلوم التطبيقية  


مقالات قد تهمك

تصفح الموسوعة

المقالات الأكثر قراءة