سلام
من امروز شروع به خوندن ماشین تورینگ کردم اما اصلا نحوه پذیرش ش رو نفمیدم اگه میشه یکی توضیح بده چون من این درس رو قبلا نگذروندم اصلا نمیفهمم
مثلا a^nb^n (^توان)
۲-چون وقت ندارم همه رو بخونم به نظر شما از انواع ماشین تورینگ لازمه کدوم رو بخونم
اول قسمت informal description این لینک رو بخونید:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
ما توی ماشین تورینگ یه نوار(tape) داریم که به سلول تقسیم شده و هر سلول شامل یک نماد از الفبای محدود است (مثل همون الفبای پشته )و یک نماد B به معنی اینکه سلول خالی است و پیش فرض هم همین خالی بودن سلول است.
ما وقتی که میخواهیم یه رشته مثلا aabb رو پردازش کنیم اون رو به این صورت توی نوار مینویسیم:
....BBBaabbBBB......
یعنی رشته رو روی نوار نوشتیم و قبل و بعد رشته هم خالی است (B)
همونطور که توی شکل (توی همون لینک مربوط به سایت wikipedia)می بینید یک هد داریم که مشخص میکنه الان روی کدوم سلول(خانه) قرار داریم و این هد میتونه به چپ و راست حرکت کنه.
حالا واسه اینکه ببینیم این رشته جزء زبانی که شما گفتید هست یا نه باید یک a رو به B تبدیل کنیم ....BBBBabbBBB......
و بعد به راست حرکت کنیم تا به b برسیم وقتی به b رسیدیم اون رو B میکنیم یعنی ....BBBBabBBBB......
و به چپ برمیگردیم تا به a بعدی برسیم اون a رو خط میزنیم (به B تبدیل میکنیم)
....BBBBBbBBBB......
و دوباره به راست میریم تا به b برسیم اون b رو هم خط میزنیم و حالا چون نوار خالی شده نتیجه میگیریم که رشته جزء زبانی که گفتید هست.
....BBBBBBBBBB......
همه این کارهایی که گفتیم یعنی حرکت به چپ و راست تشخیص محتویات سلول و خط زدن در ماشین تورینگ امکان پذیره اما انواع خاص ماشین تورینگ ممکنه یک قابلیتی رو نداشته باشند مثلا فقط بتونند به راست حرکت کنند یا نوارشون از یک طرف محدود شده باشه.یا دو تا نوار داشته باشند.
تشکر
اگر با حالت‌ها یه مقدار بیشتر توضیح بدید ممنون
این مثال رو فهمیدم ولی یه توضیح کلی میخوام که بقیه هم بتونم بفهمم
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
جدول و توضیحات زیر جدول رو نگاه کنید. (هر وضعیت رو با qi نشون میدیم.)