اتوماتون پشته ای

اتوماتون پشته ای صوری سازی این مفهوم شهودی، یک تعریف دقیق از آتاماتون پشته ای بدست می دهد. تعریف: یک پذیرندهٔ پشته ای غیر قطعی ( NPDA ) به شکل ( M= ( Q، ∑، Γ، ∂، qo، z، F
نمایش داده می شود، بطوری که در آن
• Qیک مجموعه متناهی از حالت های داخلی واحد کنترل است،
• ∑الفبای ورودی است،
• Γ یک مجموعه متناهی از نشانه ها که الفبای پشته نامیده می شود،
• ( ∂:Q× ( ∑υ{⋋} ) ×Γ تابع انتقال،
• Q0€Q حالت اولیه واحد کنترل است،
• z€Γ≤Qنشانهٔ شروع پشته است
شکل پیچیده دامنه و برد تابع انتقال نیاز به بررسی بیشتری دارد. آرگومان ∂ حالت های فعلی واحد کنترل، نشانه ورودی فعلی و نشانهٔ بالای پشته است. نتیجه یک مجموعه از زوج های ( q، x ) می باشد که در آن q حالت بعدی در واحد کنترل است. رشتهٔ x نیز به جای نشانه ای که اکنون بر روی پشته است قرار می گیرد. به خاطر داشته باشیم که دومین آرگومان∂ ممکن است برابر با⋋ باشد؛ بنابراین حرکتی که هیچ نشانه ای را از ورودی مصرف نمی کند امکان پذیر است. به چنین حرکتی، یک انتقال - ⋋ گفته می شود. همچنین ∂ طوری تعریف شده است که به نشانهٔ موجود بر روی پشته نیاز دارد. اگر پشته خالی باشد هیچ حرکتی ممکن نیست. بالاخره اینکه، برد تابع انتقال یابد باید یک زیرمجموعه محدود باشد زیرا Q×Γ نامتناهی بوده و بنابراین دارای تعداد نامتناهای زیرمجموعه است. در حالیکه یک npda ممکن است. انتخاب های زیادی برای حرکت داشته باشد، این انتخاب ها باید به یک مجموعه متناهی از حالت ها محدود باشد. فرض کنید که مجموعهٔ قانون های انتقال یک npdaشامل ∂ ( q1، a، b ) ={ ( q2، cd ) ، ( q3، ⋋ ) باشد . اگر در یک لحظهٔ مشخص، واحد کنترل در حالت q1، نشانه ورودی برابر با a و نشانه موجود در بالای پشته نیز برابر با b باشد، یکی از دو مورد زیر اتقاف می افتد: 1 ) واحد کنترل به حالت q2 می رودو رشتهٔ cd جایگزین نشانهٔ بالای پشته می شود. 2 ) واحد کنترل به حالت q3 می شود و نشانهٔ b نیز از بالای پشته حذف می شود. در این روش نشانه گذاری، اضافه کردن یک رشته به پشته، به صورت نشانه به نشانه و از انتهای راست آن رشته انجام می شود.
اتومات پشته ای با ماشین های حالات متناهی در دو چیز متفاوت اند:
1 - آن ها می توانند از قسمت بالا پشته استفاده کنند که کدان انتقال صورت گیرد.
2 - آن ها می توانند پشته را به عنوان بخشی از انجام انتقال دستکاری کنند.