ابتدای کار اگر a اومد‌، آن را درپشته پوش میکنیم،اگر b اومد دو حالت داره: ممکنه این b‌، اولین حرف رشته باشه، که به هر تعدادی که نیازه از ورودی میپذیره،(و میتوان b^q و b^s رو باهم در نظر گرفت) اما تو پشته تغییری نمیدیم،اگر به پایان رشته رسیدیم و تو استک چیزی نبود رشته پذیرفته میشه، اما اگر b بعد از a اومده باشه،به هر تعداد که بیاد از ورودی میگیریم و در پشته تغییری نمیدیم، تنها فرقش با حالت قبل اینه که ممکنه‌، بعد از a‌، b ببینه،که در این صورت تا جایی که در پشته a هست و a میاد از پشته پاپ میکنیم،اگر پشته خالی شد، و رشته تموم شد که پذیرفته میشه، اما بعد اگر b اومد و پشته خالی بود که میپذیره و تو استک چیزی نمیریزه‌، تا به پایان رشته برسیم .
هر رشته ای که جز زبان باشه میتونیم با این ساختار پیادش کنیم.

کافیه این زبان رو به صورت الحاق دو زبان زیر در نظر بگیرید:
[tex]L=\{a^{p}b^{q}a^{p}\}.\{b^{s}\}[/tex]
خیلی بدیهیه که میشه برای چنین زبانی یک ماشین پشته ای طراحی کرد

چطور میشه از رو پشته p تا a گذاشت(یا برداشت) در صورتی که بالای پشته ما ابتدا q تا b داریم؟ به تعداد p دسترسی نداریم که!!!

نمیدونم فهمیدم یا نه!!!
یعنی منظورتون این شد که اگه بعده b، a اومد b رو تو پشته وارد نمیکنیم!! آره؟ مگه نباید هرچی اومد باید با پشته پردازش بشه؟
ممنون از وقتی که گذاشتین!!

حتما نباید در پشته چیزی اضافه بشه، میتونیم تو حرکتمون به جاش لاندا بذاریم که چیزی توش اضافه نمیشه.
مثلا اگر یه ماشین dfa رو بخواهیم با npda پیاده سازی کنیم، مثل حالتی که فرضا میخواستیم ماشین حاصل از اشتراک یک زبان منظم(dfa) و زبان مستقل از متن(npda) رو تولید کنیم،برای اثبات مستقل از متن بودن زبان حاصل میگفتیم dfa رو میشه با ساختار پشته پیاده سازی کرد اما بدون اینکه چیزی تو پشته اضافه بشه....
اگه ابهامی بود بفرمایید که توضیح بیشتر بدم.