حل تمرین نظریه محاسبات/فصل دوم/حل تمرین۲-۵
حل تمرین۲-۵
تمرین
[ویرایش]حل
[ویرایش]الف) در این PDA اولین یک که می‌آید پشته خالی می‌باشد در نتیجه عدد 0 را push می‌کنیم .دومین 1 که می‌آید یک 0 در پشته داریم پس این بار برای مشخص شدن دومین 1 یک 1 در پشته push می‌کنیم. برای سومین یک که می‌آید به نتیجه مطلوب رسیده‌ایم و به حالت qf میرویم.
http://i43.tinypic.com/1z2lp93.jpg
ب) برای این ماشین ناپایانه اول را نگه می‌داریم و حدس می‌زنیم که ک به آخر رشته رسیده‌ایم. اگر با مقدار درون پشته یکی بود به حالت qf میرویم.
http://i44.tinypic.com/iol0kn.jpg
پ) در اینجا با آمدن هر ورودی متناسب با جایش در رشته که فرد باشد یا زوج به حالت q1 برای فردها و به حالت q2 برای زوج‌ها میرویم. سپس بدون خواندن ورودی از حالت فردها به حالت qf میرویم در غیر این صورت قابل قبول نمی‌باشد.
http://i42.tinypic.com/2enw6bm.jpg
ث) در اینجا هر یک که وارد می‌شود 1 را push می‌کنیم صفر که می‌آید هم اگر یک قبلش باشد pop در غیر این صورت pop می‌کنم . برای ک هم به همین حالت.
http://i43.tinypic.com/fxcb2g.jpg
ج)در اینجا یک جا حدس می‌زنیم که به وسط رشته رسیده‌ایم تا قبل از آن تمام رشته را push کرده‌ایم .حال اگر از وسط رشته pop را در صورت یکسان بودن انجام دهیم باید در انتها چیزی در پشته نماند.
http://i40.tinypic.com/2em1n3d.jpg
چ) با یک ورودی تهی به حالت نهایی میرویم.
