اتاماتای پشته‌ ای یک پذیرنده ی پشته ای غیر قطعی(npda) به  شکل( M=(Q،∑، Γ، ∂،qo،z،F  است. به طوری که در آن :

• Qیک مجموعه نامتناهی از حالت های داخلی واحد کنترل است،
• ∑الفبای ورودی است،
• Γ یک مجموعه متناهی از نشانه ها که الفبای پشته نامیده می شود،
• (∂:Q×(∑υ{⋋})×Γ تابع انتقال،
• Q0€Q حالت اولیه واحد کنترل است،
• z€Γ≤Qنشانه ی شروع پشته است

عملکرد

توصیف آنی:

توصیف آنی یک سه‌تایی منظم به فرم (q,w،α) است که در آن:

– q یک حالت باشد.

– w باقیمانده‌ی رشته‌ی ورودی باشد.

– α محتویات پشته باشد.

را یک توصیف آنی از ماشین پشته‌ای می‌نامیم.

دقت کنید که در نگارش بالا سمت چپ‌ترین نماد α، بالاترین عضو پشته است. ضمناً برای نمایش حروف الفبا معمولاً از b,a,…. ، برای نمایش حرف‌های پشته از Y,X,… و برای نمایش محتویات پشته از γ,β,αو… استفاده می‌شود.

برای درک بهتر این موضوع میتوانید به لینک زیر مراجعه کنید:

http://en.wikipedia.org/wiki/Stack-oriented_programming_language