زمان کنونی: ۰۳ تیر ۱۳۹۸, ۰۴:۱۴ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

نحوه رسم تورینگ

ارسال:
  

f.b پرسیده:

نحوه رسم تورینگ

سلام
من امروز شروع به خوندن ماشین تورینگ کردم اما اصلا نحوه پذیرش ش رو نفمیدم اگه میشه یکی توضیح بده چون من این درس رو قبلا نگذروندم اصلا نمیفهممConfused
مثلا 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......

همه این کارهایی که گفتیم یعنی حرکت به چپ و راست تشخیص محتویات سلول و خط زدن در ماشین تورینگ امکان پذیره اما انواع خاص ماشین تورینگ ممکنه یک قابلیتی رو نداشته باشند مثلا فقط بتونند به راست حرکت کنند یا نوارشون از یک طرف محدود شده باشه.یا دو تا نوار داشته باشند.

۰
ارسال:
  

f.b پاسخ داده:

RE: نحوه رسم تورینگ

تشکر
اگر با حالت‌ها یه مقدار بیشتر توضیح بدید ممنون
این مثال رو فهمیدم ولی یه توضیح کلی میخوام که بقیه هم بتونم بفهمم

۰
ارسال:
  

ف.ش پاسخ داده:

نحوه رسم تورینگ


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

جدول و توضیحات زیر جدول رو نگاه کنید. (هر وضعیت رو با qi نشون میدیم.)



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  نحوه تشخیص زبان های خطی arefeh.hp ۷ ۴,۶۲۸ ۰۹ بهمن ۱۳۹۳ ۰۱:۰۵ ق.ظ
آخرین ارسال: nazanin2020
  تشخیص نوع گرامر و نحوه ی کار alirezafchh ۱ ۷۰۴ ۱۰ دى ۱۳۹۳ ۰۷:۳۲ ب.ظ
آخرین ارسال: Hamid_0311
  نحوه و روش تقسیم دو زبان s_t_6 ۴ ۷۲۰ ۱۵ مرداد ۱۳۹۳ ۱۲:۴۸ ق.ظ
آخرین ارسال: fatemeh69
Smile گراف رسم شده برای این زبان منظم چه ایرادی دارد و چرا s_t_6 ۸ ۱,۵۶۰ ۳۱ تیر ۱۳۹۳ ۰۶:۱۶ ب.ظ
آخرین ارسال: Jooybari
  نحوه پیدا کردن اشتراک دو زبان sonia11 ۸ ۱,۵۰۱ ۱۸ بهمن ۱۳۹۲ ۱۱:۰۳ ب.ظ
آخرین ارسال: sonia11
  سوال در مورد نحوه محاسبه خروجی چندتا عبارت منظم iBimS ۱ ۸۶۸ ۳۰ اردیبهشت ۱۳۹۲ ۰۱:۳۳ ق.ظ
آخرین ارسال: Jooybari
Question رسم dfa مربوط به L1/L2 : مثال ۴-۴ از کتاب لینز g_monireh ۵ ۱,۹۴۷ ۲۹ اردیبهشت ۱۳۹۲ ۰۲:۰۲ ب.ظ
آخرین ارسال: g_monireh
  رسم dfa برای این سوال؟ post98 ۴ ۱,۴۴۵ ۲۳ فروردین ۱۳۹۲ ۰۹:۲۴ ب.ظ
آخرین ارسال: Jooybari
Lightbulb رسم dfa برای عبارت منظم Eternal ۲ ۱,۶۳۲ ۱۴ دى ۱۳۹۱ ۱۲:۲۶ ق.ظ
آخرین ارسال: Eternal
  کمک در نحوه حل سوال ۱۵ بخش دوم فصل۱ لینز samaneh_aftab ۲ ۸۸۰ ۱۳ تیر ۱۳۹۱ ۰۲:۱۸ ب.ظ
آخرین ارسال: samaneh_aftab

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close