در سوال ۵۸ ماشین یه صفر و پشت اون هر چند تا صفر که بیاید رو می پذیره که گزینه ۱ این قابلیت رو نداره و همچنین ماشین رشته ای به فرم * (۱۱)۱ رو می پذیره که گزینه ۲ هم این رشته رو پوشش نمیده و گزینه ۴ هم لاندا رو می پذیره که ماشین این رشته رو در بر نمیگیره به نظرم باید گزینه ۳ درست باشه.

خودم به نتیجه رسیدم...
سوال ۵۷ صورت سوالش مشکل داره و وقتی که b رو می خونه و بجاش y می ذاره و به سمت چپ میره، در q3 باید X رو بخونه و به سمت راست بره که چنین حالتی رو در q3 نداره پس شکل اشتباه هستش یا اصلا هیچ گزینه ای صحیح نیست...

tu halate q3 va x mire be halate q3 va x va L ke ba estefade az enteghale halat q3 va namade khonsa mire q0 va khonsa va R mitooni azash estefade koni

(۲۲ مهر ۱۳۹۰ ۰۱:۰۹ ب.ظ)amir2930 نوشته شده توسط:  tu halate q3 va x mire be halate q3 va x va L ke ba estefade az enteghale halat q3 va namade khonsa mire q0 va khonsa va R mitooni azash estefade koni

مرسی از پاسختان
اما اگه ممکنه فارسی بنویسید و در ضمن در رشته مثالی که من گفتم لامبدا نداریم و خود ماشینم لامبدا تولید نمی کنه. پس نمی تونیم به q0 بریم!!!
پس سوال مشکل داره و باید حذف بشه

منظورم رو فکر کنم متوجه نشدید...
شما رشته مثلا aaabbb رو در نظر بگیر
اولین a با X خوردن میره راست و اولین b را X خوردن میره چپ تا میرسه به X اول که روی a خورده بود.
خب حالا باید X رو بخونه بره راست که در q3 چنین چیزی نیست.
پس همونجا متوقف می شه.
اگه اولی رو با لامبدا می خوند و میرفت راست باز یه چیزی که اونم باز به مشکل برمی خوره...

(۲۳ مهر ۱۳۹۰ ۱۲:۵۹ ب.ظ)پشتکار نوشته شده توسط:  منظورم رو فکر کنم متوجه نشدید...
شما رشته مثلا aaabbb رو در نظر بگیر
اولین a با X خوردن میره راست و اولین b را X خوردن میره چپ تا میرسه به X اول که روی a خورده بود.
خب حالا باید X رو بخونه بره راست که در q3 چنین چیزی نیست.
پس همونجا متوقف می شه.
اگه اولی رو با لامبدا می خوند و میرفت راست باز یه چیزی که اونم باز به مشکل برمی خوره...

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

حل تشریحی

بالاخره سوال ۵۷ حل شد و با تشکر از دوست خوبم amir2930
با توجه به اینکه در کتاب مایکل سیپسر سمت چپ ماشین تورینگ رو بسته شده فرض کرده و این سوال از کتابهای لینز یا سود کامپه که سمت چپ نوار رو بی نهایت فرض کرده به بررسی گزینه‌ها پرداختم و نتیجه زیر حاصل شد:
رد گزینه ۱» اگه رشته ای با b شروع بشه توسط ماشین پذیرفته هست که در گزینه یک این عامل وجود نداره و همه رشته‌ها با a شروع می شن.
رد گزینه ۲» رشته aabbaa رو امتحان کنید!
رد گزینه ۴» رشته ساده aaa در زبان وجود داره که توسط آتوماتا پذیرفته نیست
پس گزینه ۳ گزینه صحیحه