ماشین های پشته ای
سلام. وقتتون بخیر و شادی. محمدرضا احمدآبادی هستم با جلسه 20 آموزش نظریه در خدمتتون هستم . امروز قصد دارم در مورد ماشین های پشته ای بهتون آموزش بدم.
ماشین های پشته ای: (push down automata )
اگر جلسات گذشته را به خاطر داشته باشید ( که بعید میدانم ) در مورد زبان های منظم و غیر منظم باهم خیلی بحث و دعوا داشتیم تا این که در جلسه نوزدهم آموزش بالاخره پرونده زبان های منظم و غیر منظم را براتون بستم و بهتون گفتم که اگر زبانی منظم بود راه شناخت اون چی هست و اگر زبانی غیر منظم بود راه شناخت اون چی هست. خب با این حرفا میشه گفت که بسیاری از زبان ها جزء دسته زبان های منظم نیستند و به هیچ عنوان نمیشود برای آن ها ماشین متناهی رسم کرد . مثل زبان anbn معروف خودمون، زیرا در ماشین های متناهی هیچ ابزاری برای کنترل تعداد سمبل های a و b و موازنه آن ها وجود ندارد. ماشین های پشته ای برای دسته ای از زبان ها به نام زبان های مستقل از متن توصیف میشوند. در مدل این ماشین علاوه بر نوار ورودی و نوار کنترل کننده وضعیت از یک پشته هم استفاده میشود . این پشته باعث میشود که بتوانیم در یک لحظه تعداد دو تا از سمبل های الفبارا موازنه یا کنترل کنیم . مدل یک ماشین پشته ای به شکل زیر خواهد بود.
خب تا اینجا من داشتم میگفتم که ماشین های پشته ای به چه دردی از زندگی ما میخورد، که فهمیدیم برای اون دنیا شاید مفید نباشه اما برای این دنیا در بعضی مواقع گره گشا خواهد بود.
تعریف ماشین های پشته ای:
هر ماشین پشته ای یک هفت تایی به فرم زیر می باشد که هرکدام از موارد به توضیح گفته شده.
فرمت مخصوص ماشین pda
FԑQ : مجموعه غیر تهی حالت های پایانی ماشین است.
در ماشین های پشته ای توابع انتقال بدین شکل توصیف میشوند که هر حالت از ماشین با توجه به سمبل جاری رشته ورودی و سمبل بالایی پشته به چه حالت دیگری منتقل شده و چه تغییری در پشته ایجاد میکند . در مورد اعمالی که در پشته های ماشین های PDA صورت میگیرد میتوان حالت های زیر را در نظر گرفت .
1- اضافه کردن یک سمبل به بالای پشته با دیدن سمبل جاری رشته ورودی (push ):
ᵟ(qi,a,x)=(qj,yx)
اگر متوجه تصویر نشدید پس به توضیحات من گوش کنید . تابع انتقالی که برای شما مثال زدم راباید اینگونه بخوانید
اگر در رشته ورودی سمبل a را مشاهده کردی و بالای پشته سمبل x بود انگاه نوار وضعیت یک خانه به جلو حرکت کرده و سمبل y را روی سمبل x ، push کن و برو به تابع انتقال بعدی.یعنی از حالت qi برو به حالت qj با این شرایط.
2- برداشتن یک سمبل از بالای پشته با دیدن سمبل جاری رشته ورودی (POP) :
ᵟ(qi,a,x)=(qj,λ)
این تابع انتقال داره میگه : اگر نوار کنترل کننده وضعیت به سمبل a اشاره کند و سمبل بالای پشته x باشد ان گاه برو به تابع انتقال بعدی و از روی پشته یک سمبل را pop کن و در رشته ورودی یک سممبل به جلو برو.
3-جایگزین کردن یک سمبل به جای سمبل بالای رشته با دیدن سمبل جاری رشته ورودی.
ᵟ(qi,a,x)=(qj,y)
این تابع انتقال میگوید: اگرنوار کنترل وضعیت در رشته ورودی سمبل a را ببیند و سمبل بالای پشته x باشد آنگاه باید سمبل x را پاک کرده و سمبل y را (در پشته) جایگزین کند.
پس اعمال روی پشته این سه مورد میباشد که از شکل و شمایل این توابع باید نوع عمل را تشخیص بدهید. یا مثل من میتونید برای خودتون کدگذاری کنید به این ترتیب که اگر تابع انتقال دو سمبل داشته باشد این عمل push خواهد بود و سمبل سمت اول به روی سمبل دوم push میشود. اگر تابع انتقال دارای یک سمبل بود عمل تعویض را نشان میدهد که سمبل ذکر شده در تابع به جای سمبل بالای پشته نوشته خواهد شد اگر تابع انتقال λ باشد این عمل pop کردن را نشان میدهد
نکته: در ماشین های پشته ای به ازای اجرای هر بار یک تابع انتقال هد رشته ورودی تنها یک واحد به سمت جلو حرکت میکند در ماشین های پشته ای فرض میشود که انتهای رشته ورودی سمبل λ قرار دارد.
الفبای پشته میتواند با الفبای ورودی ماشین یکسان باشد و یا با الفبای ورودی ماشین متفاوت باشد . (هرچند بهتر است متفاوت در نظر گرفته شود.)
نکته: در ماشین های پشته ای هنگامی یک رشته توسط ماشین پذیرفته میشود که ماشین در یکی از حالات پایانی بوده وهد ورودی در انتهای رشته ورودی باشد . در این وضعیت محتوای داخل پشته اهمیتی ندارد. در مورد ماشین های پشته ای نیز میتوان هر ماشین را با یک گراف وضعیت توصیف کرد به طور مثال تابع انتقال زیر به شکل زیر نمایش داده میشود:
ᵟ(qi,a,x)=(qj,a)
برای طراحی یک ماشین پشته ای برای یک زبان همیشه فرض میکنیم در ابتدای کار ، ماشین در حالت شروع (Q0) قرار دارد و در این حالت هد پشته به سمبل Z ( سمبل آخر پشته ) اشاره میکند . با تنظیم توابع انتقال و استفاده از پشته ماشین طراحی میکنیم که تمامی رشته های عضو زبان را پذیرفته وهیچ رشته ای را که عضو زبان نیست نپذیرد.
واما بریم سراغ مثال .
برای زبان های زیر یک PDA طراحی کنید.
L1={anbn| n>=0}
روش حل این گونه سوالات:
برای حل ماشین های پشته ای و طراحی اون ها بهتره از همون ابتدا دست به قلم نشوید . اول با خودتون فکر کنید برای این زبان گفته میشه ماشین پشته ای رسم کرد؟ جواب این سوال را باید با ذهنتون پیدا کنید و ببینید عناصر یا سمبل های رشته های مورد پذیرش این زبان با پشته قابل کنترل هست یا نه؟ اگه قابل کنترل بود که حله و گرنه نمیتونیم برای اون زبان pda رسم کنیم.
مثلا برای همین زبان L1 میخواهم ببینم میتونم این زبان را با ماشین پشته ای پیاده سازی کنم یا خیر. طبق حرف های اول جلسه گفتیم این زبان را نمیتوان برایش ماشین متناهی رسم کرد چون به هیچ طریقی نمیتوانیم سمبل های a و b را کنترل کنیم .اما در ماشین پشته ای من میگم از اول رشته که به من داده میشه ، به ازای هر سمبل a که میبینم یه سمبلی مثل 1 را روی پشته push میکنم . حالا به محض اینکه اولین سمبل b را دیدم از روی پشته pop میکنم و به همین ترتیب به جلو حرکت می کنم و به ازای هر سمبل b که میبینم این 1 هارا حذف میکنم اگر رشته ورودی تمام شد و به عنصر z پشته هم رسیدم یعنی این رشته مورد پذیرش این ماشین هست در غیر این صورت (یعنی اگر رشته زودتر از پشته به انتها رسید و یا پشته زودتر از رشته ورودی به انتها رسید )این رشته مورد پذیرش این ماشین نخواهد بود
من به پاراگراف بالا میگم ایده پیاده سازی ماشین پشته ای. پس برای هر زبانی ما باید در اولین گام ایده پیاده سازی اون را برای خودمون تشریح کنیم حالا بر اساس همین ایده ماشین را براتون رسم میکنم.
گفتیم همیشه ماشین pda باید از حالت شروع با q0 شروع شود. خب اینم از q0 :
حالا باید توابع انتقال این حالت را بنویسیم.
خوب به این حرفی که الان میخواهم بگویم گوش کنید . در ابتدا برای شروع سمبل جاری پشته Z هست و من از رشته ورودی سمبل a را میبینم پس باید در تابع انتقالی که میخواهم روی این حالت بنویسم ، بگویم اگر بالای پشته z باشد و سمبل جاری a باشد انگاه یک واحد روی رشته ورودی به جلو برو وعدد 1 را روی پشته push کن . حالا این تابع انتقال باید به چه حالتی برود؟
دو حالت در این جا داریم یا سمبل بعد از این سمبل b خواهد بود ویا باز هم a را مشاهده خواهیم کرد . اگر a را مشاهده کردیم پس یعنی دو باره به سمبل a رسیدیم و باید عمل قبل را انجام دهیم پس به همین حالت دوباره بر میگردیم.
سمبل دوم رشته ورودی اگر سمبل a باشد پس یعنی هنوز سمبل های a ادامه دارند وباید به ازای هر سمبل a روی پشته سمبل 1 را push کنیم. اما از سمبل دوم به بعد دیگر بالای پشته سمبل z نخواهد بود پس تابع انتقال بالا فقط برای حالت شروع مناسب است وبرای سمبل دوم به بعد جواب نمیدهد اما تعویض حالت هم نیازی نیست پس یک تابع انتقال دیگر روی همین حالت مینویسم با این توضیح که اگر سمبل جاری رشته ورودی a باشد و سمبل بالای پشته 1 باشد آنگاه از رشته ورودی یک واحد به جلو حرکت کن و سمبل 1 را بالای پشته push کن .
تا اینجا تونستیم تکلیف دیدن سمبل های a را مشخص کنیم . حالا نوبت به این میرسدکه بعد از سمبل های a سمبل b را ببینیم . وقتی من قرار هست سمبل b راببینم باید از روی پشته pop کنم . پس خواهیم داشت:
این تابع انتقال فقط اولین سمبل b را که مشاهده کرد از روی پشته عمل pop را انجام میدهد. اما بقیه سمبل های b هم باید برایشان عمل pop صورت گیرد. پس همین تابع انتقال رادوباره باید از حالت q1 بنویسم اما به چه حالتی ؟ در جواب باید عرض کنم اگر تعداد b را میدانید یا فکر میکنید یه دونه دیگر هست پس به یه حالت جدید بروید اما اگر مثل من فکر میکنید که نمیدانید چه تعدادسمبل b قرار است مشاهده کنید بهتر است از حلقه استفاده کنید و از حالت q1 به خودش بروید تا زمانی که سمبل های b تمام شود.
خب این از سمبل های a و b . گفته بودم که در ماشین های پشته ای انتهای رشته فرض بر این هست که λ قرار دارد. برای این ماشین ما هنوز حالت پایانی ترسیم نکردیم اگر به انتهای رشته رسیدیم یعنی لامبدا را دیدیم و همین طور در پشته z را مشاهده کردیم یعنی تعداد سمبل هایa و b رشته ورودی باهم برابر بوده پس مورد پذیرش این ماشین باید قرار گیرد. این جمله هایی که من گفتم را باید به صورت یه تابع انتقال رسم کنیم. که میشود:
خب این از ماشین پشته ای این زبان .تا الان میشه گفت این ماشین 99 درصد رشته مورد پذیرش این زبان را قبول میکند . اما چرا 99 درصد؟
بله حدستون درست بود این زبان رشته لامبدا را میپذیرد. پس ماشینی که ما طراحی کردیم ناقص است . برای این حل این نقص من باید یک فرض رشته تهی را از همان ابتدا انجام دهم . و باید بگم اگر در حالت شروع رشته تهی رادیدم و همچنین سمبل بالای پشته Z بود آنگاه به حالت پایانی یک انتقال بااین تابع انتقال باید رسم کنم. پس شکل نهایی ماشین پشته ای این زبان خواهد شد:
خب برای این جلسه دیگه کافیه . این مباحثی که امروز براتون گفتم را مرور کنید به همراه حل دوباره همین مثال تا بتونید جلسه آینده حرف های منو راحت تر متوجه بشید. در جلسه آینده قصد دارم مثال های ماشین پشته ای را باهم بررسی کنیم.
شادوسربلند و موفق باشید ....
تاجلسه آینده خدانگهدار.
نظرات کاربران