حل مثال های ماشین های PDA

سلام . محمدرضا احمدآبادی هستم با جلسه 21 آموزش نظریه زبان ها در خدمتتون هستم ، طبق قولی که در جلسه گذشته بهتون داده بودم این جلسه قرارمون این هست که مثال های ماشین هایPDA را باهم بررسی و حل کنیم. پس بدون فوت وقت میریم برای مثال ها.
مثال ) برای زبان های زیر PDA مناسب طراحی کنید.

 L2={anbmck|k=n+m}

قرارمون این بود که برای این دسته از سوالات  اول یه ایده پیاده سازی ماشین( یک سبک راه حل با پشته) برای خودمون بگیم بعد همون ایده را پیاده سازی کنیم. ایده ای که به نظر شما میرسه برای این زبان چی هست؟
ایده ای که به ذهن من رسیده این هست که به ازای هر سمبل a که میبینم 1 روی پشته push  میکنم و همین طور به ازای هر سمبل b هم که میبینم باز 1 روی پشته push  میکنم. حالا میرسم به سمبل c، به ازای هر c که میبینم عمل pop را انجام میدهم. اگر رشته ورودی به اتمام رسید یعنی سمبل انتهای رشته λ بود و پشته هم تهی بود آن موقع میگویم که رشته ورودی برای این زبان قابل پذیرش هست ودرغیر این صورت این رشته متعلق به این زبان نخواهد بود.
این از ایده پیاده سازی این ماشین . حالا بریم این ایده را جامه عمل بپوشانیم.
در ابتدا من یا سمبل a را میبینم و یا سمبل b . لطفا این جمله را در گوشه ذهنتان نگه دارید.
موقعی که من اولین سمبلa را میبینم پشته تهی هست پس باید 1 را روی پشته تهی push  کنم . و بعد از ان مثل مثال جلسه قبل ممکنه بازهم سمبل a را ببینم پس این قاعده که من گفتم برای اولین سمبل درست خواهد بود و برای سمبل های دوم به بعد a  باید قاعده ای جدید بنویسم به فرم a,1/11 . تا به این مرحله ماشین PDA من به این شکل خواهد بود.
 

حالاکه من همه سمبل های a را دیدم میرسم به سمبل b . وقتی من از سمبل های a گذر میکنم دراین حالت عنصر بالای پشته 1 خواهد بود پس من باید به ازای هر سمبل b که میبینم 1 روی پشته push کنم. که این قاعده خواهد شد:  b,1/11. تا به این جا ماشین پشته ای ما خواهد بود:
 

حالا برگردیم به اول حل مثال. گفته بودم من در ابتدای رشته یا سمبل a را خواهم دید و یا سمبل b. در صورت وجود سمبل a  تقریبا تمام حالت های مورد اتفاق را بررسی کردیم . اما ممکن هست که اصلا در ابتدای رشته سمبل a ما نبینیم. پس اولین سمبل b خواهد بود. در این حالت عنصر بالای پشته تهی خواهد بود پس باید 1 روی تهی push  شود. پس قاعده آن خواهد شد: b,z/1z
بعد از مشاهده اولین سمبل b مطمئنا 1 در بالای پشته خواهد بود پس به ازای مشاهده هر سمبل b (b دوم به بعد )باید 1روی 1 push  کنیم. که میشود:b,1/11  .
 

حالا ما تمام سمبل های a و b را مشاهده کردیم نوبت به دیدن سمبل c میرسد که باید باهربار دیدن این سمبل یک عملpop از روی پشته انجام دهیم. به محض اینکه ماشین اولین سمبل c را دید فورا با یه تابع انتقال به حالت جدید میرود و با آن حالت جدید تمام سمبل های c بعد آن را مشاهده کرده و عمل pop روی پشته انجام خواهم داد. با این تابع c,1/λ.
 

مسلما در انتها باید به حالتی برسیم که بالای پشته z باشد یعنی پشته تهی باشد و انتهای رشته λ باشد . اگر این شرایط اتفاق افتاد ( همه باهم) به حالت پایانی میرویم .
 

این تقریبا پیاده سازی ایده بود اما کار هنوز تمام نشده. و باید حالت های استثنا را لحاظ کنیم. مثلا اولین استثنا اینکه ممکنه بعد از سمبل a من اصلا سمبل b در رشته نداشته باشم مثل رشته aaaccc . این رشته جزء رشته های مورد پذیرش این زبان هست اما مورد پذیرش ماشین نیست چون در مورد نبود b اصلا صحبت نکرده و اجبارا باید سمبل b وجود داشته باشد . پس برای این حالت استثنا از حالت q0 با یه انتقال pop متصل میکنیم به حالت q2
.  

خب باز داستان ادامه دارد. اگر باور نمیکنید به این سوال من جواب بدید: رشته λ ایا مورد پذیرش زبان و ماشین رسم شده اش هست؟
مسلما همتون دارید به این فکر میکنید که مورد پذیرش زبان هست اما نمیتونید با ماشین این پذیرش را نشان دهید. بله حق باشماست چون این ماشین که مارسم کرده ایم رشته تهی را نمیپذیرد. برای این که رشته تهی مورد پذیرش این زبان باشد باید یک انتقال از حالت q0 به حالت q3 با قاعده :  λ,z/z رسم کنیم .
 

حالا میتونید بگید که این ماشین، ماشین درست زبان l2 میباشد.

 L3={anb2n | n>=0}

ایده پیاده سازی ماشین این زبان چی به نظرتون میرسه؟
ایده: برای گفتن ایده لازم هست که بفهمیم این زبان اصلا داره چی میگه؟ این زبان میگه که به ازای هر یه دونه سمبل a باید دوعدد سمبل b وجود داشته باشد . خب ایده ای که من میخواهم برایتان بگویم به این شرح است. به ازای دیدن هر یک سمبل a من دوعدد 1 را روی پشته push  میکنم  و وقتی به سمبل b رسیدم به ازای دیدن هر سمبل b یک pop  روی پشته انجام میدهم. تا موقعی که به انتهای رشته برسم . وقتی به انتهای رشته ورودی رسیدم واگر بالای پشته عنصری وجود نداشته باشد آنگاه رشته ورودی مورد پذیرش زبان خواهد بود در غیر این صورت این رشته مورد پذیرش این زبان نخواهد بود.
این از ایده پیاده سازی ماشین. حالا باتوجه به این ایده من شروع میکنم به رسم ماشین pda.
من موقعی که اولین سمبل a را مشاهده میکنم باید بالای پشته 11  را push  کنم. پس اولین تابع انتقال این ماشین با فرض دیدن اولین سمبل a خواهد بود:  a,z/11z . حالا بعد از دیدن اولین سمبل a نوبت به دیدن سمبل دوم و مابقی سمبل های a میباشد که باید به ازای دیدن هرسمبل طبق ایده پیاده سازی 11  را روی 1 push کنم. تابع انتقال این عمل خواهد بود: a,1/111  
 

تا اینجا تقریبا تکلیف مشاهده سمبل a مشخص شد. حالا نوبت به دیدن سمبل b میرسد . طبق ایده گفته شده من موقعی که سمبل b را مشاهده میکنم باید از بالای پشته یک عمل pop  یک عنصری انجام دهم. یعنی تابع انتقال این حالت میشود: b,1/λ .
 

حالا که تمام سمبل های a,b را مشاهده کردیم نوبت به شرط پایانی میرسه یعنی موقعی که من اخرین سمبل b را مشاهده کردم وعمل pop را انجام دادم  اگر بالای پشته z  (تهی) باشد یعنی رشته مورد پذیرش ماشین خواهد بود. پس حالت پایانی ماشین این زبان خواهد بود:
 

اما اینجا پایان ماجرا نیست اگر به زبان دقت کنید رشته تهی مورد پذیرش این زبان میباشد اما مورد پذیرش این ماشین نیست . برای اینکه این نقص برطرف شود باید یک انتقال از حالت q0 به حالت q2 با تابع انتقال λ,z/z  انجام دهیم. پس شکل نهایی ماشین pda این زبان خواهد شد:

 L4={anbn+mcm| n>=0,m>0}

برای این زبان چه ایده پیاده سازی به ذهنتون میرسه؟  تعداد b باید برابر با تعداد a,c باشه . اما چطوری با پشته بتونیم این تعداد را کنترل کنیم؟
ایده ای که به ذهن من میرسه این طوری هست : من به تعداد سمبل های a که مشاهده میکنم 1 روی پشته push  میکنم بعد موقعی که به اولین سمبل b رسیدم شروع به انجام عمل pop  میکنم تا زمانی که پشته تهی بشه مسلما در این حالت هنوز سمبل b باقی مونده که ندیدم حالا موقعی که به پشته تهی میرسم از این مرحله به ازای هر سمبل b که میبینم به جای اینکه عمل pop روی پشته انجام دهم 1 روی پشته push میکنم تا به اولین سمبل c برسم . موقعی که اولین سمبل c را دیدم شروع میکنم از بالای پشته عمل pop را انجام میدهم تا زمانی که به انتهای رشته ورودی برسم و پشته تهی شود در این حالت خواهد بودکه رشته مورد پذیرش زبان است. ممکن هست که من از ابتدا اصلا سمبل a را نبینم و رشته ورودی با سمبل b شروع شود که باز مثل حالتی که توضیح دادم به ازای هرسمبل b سمبل 1 را روی پشته push خواهم کرد و موقعی که به سمبل c رسیدم دوباره عمل pop را انجام خواهم داد. حداقل رشته ورودی این زبان میتواند bc باشد زیرا اجازه صفر بودن مقدار m در زبان داده نشده پس رشته  λ مورد پذیرش این زبان نخواهد بود. با این توضیحات میرویم سراغ رسم ماشین PDA این زبان .
برای رسم ماشین پشته ای این زبان اول فرض کنید رشته های ورودی سمبل a را داشته باشند . خب من اولین سمبل a را که میبینم بالای پشته تهی است پس باید طبق قاعده    a,z|1z یک انتقال داشته باشم برای سمبل دوم به بعد a  هم باید یک انتقال با قاعده ای جدید به دلایل گفته شده در مثال های قبل داشته باشم که قاعده تولید این انتقال خواهد بود:  a,1|11 پس تا به اینجا ماشین این زبان خواهد شد:
 

تا به اینجا تمام سمبل های a در رشته ورودی را مشاهده میکنم حالا نوبت به مشاهده سمبل b هست پس احتیاج به یک حالت جدید دارم تا بتوانم با دیدن سمبل b عمل pop را انجام دهم . من باید انقدر سمبل b ببینم تا به تعداد سمبل های a عمل pop روی پشته انجام دهم خب قاعده تولید این انتقال خواهد بود:   b,1|1λ .
 

در این جا دیگه بالای پشته سمبل 1 وجود ندارد و پشته خالی است اما هنوز سمبل b وجود دارد در این مرحله به جای عمل pop از پشته نوبت به عمل push روی رشته میشود . باهربار دیدن سمبل b من 1 روی پشته  push   میکنم. با قاعده :  b,z|1z .  این قاعده برای دیدن اولین سمبل b بعد از تهی شدن پشته می باشد اما برای دیدن سمبل دوم به بعد b در رشته دیگر این قاعده کار نمیکند (چرا؟) پس باید تابع انتقال جدیدی بنویسیم که بتواند سمبل های b بعد اولین سمبل b را مشاهده و ثبت کند که این قاعده تولید خواهد شد:  b,1|11. پس تا به این جا ماشین پشته ای این زبان خواهد شد:
 

خب تا اینجا تکلیف سمبل های a,b مشخص شد. حالا نوبت به سمبل c میرسد . ماشین باید به محض این که اولین سمبل c را مشاهده کرد دوباره از بالای پشته شروع به عمل pop کند تا زمانی که به انتهای رشته ورودی برسد و همزمان بالای پشته عنصری وجود نداشته باشد در این حالت رشته ورودی مورد پذیرش زبان و ماشین خواهد بود.
 

حالا باید شرط سوال را برای این ماشین به عنوان حالت پایانی رسم کنیم . یعنی بالای پشته تهی باشد و عنصر انتهای رشته ورودی  λ باشد .
 

تا به این جا میتوان گفت که 90 درصد رسم ماشین انجام شده است ومانده 10 در صد پایانی. این 10 درصد پایانی برمیگردد به جمله اول رسم ماشین که گفته بودم فرض کنید رشته ورودی با سمبل a شروع شود. حالا باید تکلیف رشته هایی که سمبل a را ندارند روشن کنیم. مسلما چون سمبل a را نمیبینیم پس نباید عمل pop برای دیدن سمبل b انجام دهیم و باید با دیدن اولین سمبل b تا دیدن اولین سمبل c عمل  push روی پشته انجام دهیم پس باید از حالت q0 به حالت q2 یک انتقال رسم کرده و قاعده تولید این تابع خواهد بود: b,z|1z .
 

و اما بریم سراغ آخرین مثال این جلسه.

 L4={anbmcmdn|n,m>0}

برای این زبان چه ایده ای به ذهنتان میرسد؟
خواهشا دنبال راه سخت نگردید. یک راه ساده برایتان میگویم. به ازای هر سمبل a که ماشین میبیند سمبل1 را روی پشته push میکند . موقعی که سمبل b را در رشته میبینیم حالا باید سمبل 0 را روی پشته push کنیم. بعد که سمبل c را دیدید به ازای هر سمبل c ازبالای پشته عمل pop را انجام میدهید زیرا تعداد سمبل های b و c  باید برابر باشد پس به ازای سمبل 0 که روی پشته push کردید عمل pop را انجام خواهیم داد. حال نوبت به سمبل d میرسد که باهربار دیدن این سمبل  عمل pop را برای سمبل 1 بالای پشته انجام میدهیم. اگر به انتهای رشته رسیدیم و بالای پشته تهی بود یعنی رشته مورد پذیرش زبان و ماشین می باشد در غیر این صورت رشته ورودی رشته مورد پذیرش این زبان نخواهد بود.
حال برویم سراغ پیاده سازی ایده.
در حالت ابتدایی من باید سمبل a را مشاهده کنم حال خواه یک سمبل و خواه چند سمبل . پس مثل مثال های قبل یک حالت رسم کرده و توابع انتقال این حالت را رسم میکنیم.
 

بعد از اینکه تکلیف سمبل a مشخص شد نوبت به دیدن سمبل های b میرسد . در این جا به توضیحی که میگویم خوب گوش کنید. فرق این ماشین با ماشین های قبل این است که در زبان های قبل با دیدن سمبل b عمل pop  را انجام میدادیم اما این بار برخلاف گذشته باید عمل push را انجام دهیم اما چون برای ما تعداد مساوی بودن سمبل های b,c مهم هست نمیتوانیم با سمبلی که a را نشانه گذاری کردیم عمل push را انجام دهیم پس باید سمبل را تغییر دهیم. برای سمبل b ماسمبل 0 را به عنوان نشانه این سمبل انتخاب میکنیم. پس به ازای دیدن هر بار سمبل b سمبل 0 را روی پشته push  خواهیم کرد .موقعی که ماشین اولین سمبل b را میبیندبالای پشته سمبل 1 وجود دارد. پس  تابع انتقال این حالت خواهد شد: b,1|01
 

حالا باید یه تابع انتقال برای سمبل دوم به بعد بنویسیم. خب برای این کار بالای پشته الان سمبل 0 وجود دارد پس به ازای هر سمبل b که ماشین مشاهده میکند سمبل 0 را روی سمبل0 بالای پشته push میکند. پس تا به اینجا خواهیم داشت:
 

تا به اینجا ما سمبل های a و b رشته ورودی را با ماشین پشت سر گذاشتیم حالا میرسیم به سمبل c که بادیدن این سمبل به ازای هربار دیدن یک عمل pop  روی پشته روی عنصر 0 انجام میدهیم. زیرا تعداد سمبل های c باید برابر تعداد سمبل b باشد. پس خواهیم داشت:
 

در این مرحله میرسیم به سمبل d خب همان طور که در ایده پیاده سازی ماشین پشته ای این زبان گفتم بادیدن سمبل d باید از بالای پشته سمبل 1 را pop کنیم زیرا تعداد سمبل های d برابر با سمبل a می باشد. پس شرط ما برای pop کردن با دیدن سمبل d این خواهد بود که 1 بالای پشته باشد.
 

حالا باید حالت پایانی ماشین را با شرط خاتمه آن رسم کنیم. شرط خاتمه این هست که اولا بالای پشته تهی باشد و ثانیا همزمان انتهای رشته  λ باشد. آنگاه رشته ورودی مورد پذیرش زبان و ماشین خواهد بود. پس حالت پایانی در ماشین خواهد شد:
 

خب حالا بریم سراغ استثنائات سوال، این زبان که رشته  λ را نمیپذیرد پس احتیاج به انتقال برای تولید  λ ندارد. و همون طور که میدانیدهیچ کدام از سمبل های زبان اجازه نیامدن در رشته ورودی را ندارند و حداقل یکبار باید هر سمبل در رشته ورودی آمده باشد. پس حالت استثنا وجود ندارد و ماشین بالا یک ماشین پشته ای کامل و درست برای زبان سوال می باشد.
 مثال های این جلسه در اینجا به پایان میرسد  اما قبل از خداحافظی میخواهم یک نصیحت برایتان بگویم تقریبا همه شما موقعی که من مثال هارا برایتان می آوردم به نظرتان مثال های سختی می آمد اما دیدید که من مثال هارا خرد میکردم و سمبل به سمبل میرفتم جلو و درنهایت میدید که خود به خود کل سوال حل شده. درست مثل جنگ و  دعوا . شما هیچ وقت نمیتونید همزمان با چند نفر درگیر شوید اما میتونید اون چند نفر را به صورت تک تک بیاورید به محله خودتان و از خجالتشان در بیایید.  موقعی هم که میخواهید این سوال ها را حل کنید سمبل هارا دونه به دونه بیاورید به محله خودتان و ضربه فنی کنید این طوری کل سوال به راحتی حل میشود.
البته اینکه نحوه دعوا کردن را گفتم صرفا یک شوخی بود اما  خواستم برایتان یک مثال از دنیای واقعی آورده باشم تا هم روش حل سوال در ذهنتان بماند و هم یک شوخی با شما کرده باشم. مطمئنا  همه شما تا چند سال دیگه این درس را فراموش خواهید کرد اما قول میدم به شما که هیچ وقت این روشی که در پاراگراف بالا برایتان گفتم را فراموش نکنید.
خب در اینجا به پایان این جلسه آموزش میرسیم . تمرین و حل سوال فراموش نشود  
تا جلسه آینده خدانگهدار.