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

تورینگ

ارسال:
  

professional پرسیده:

تورینگ

با سلام

دوستان لطفا اگر میتونید برای من این مثال رو توضیح بدید.
این همه دوباره کاری برای چیه؟ کتاب راه حل رو توضیح داده اما خیلی گنگه!


فایل‌(های) پیوست شده

۱
ارسال:
  

بنده ی خدا پاسخ داده:

تورینگ

برای حل سوال های ماشین تورینگ کافیه که یک مثال بزنید و آن مثال را اگر جواب دارید بیاندازید توی ماشین و ببینید چه بر سرش می آید تا ایده ماشین را بگیرید. اگر هم جواب ندارید یک ایده برایش بسازید منتهی بعد از کشیدن طراحی ایده ی تان حتما یک حالتی را جواب نیست را به طراحی بدهید تا مبادا چیز اشتباهی را بپذیرد.
اما درباره ی این سوال جواب کتاب را توضیح می دهیم:

شکل رسم شده در واقع سه قسمت اصلی داره،
قسمت یک ( q0 , q1 ,q2 ,q3 ) : این قسمت عبارتی که دارید رو به صفر یک تبدیل می کنه تا هد رو در قسمتی قرار بده که عبارت به دو قسمت مساوی تقسیم بشه (توجه تان را جلب می کنم که طول هر عبارت در ww حتما زوج است). یعنی اگر مثلا داشته باشیم abbabb آخر این قسمت داریم ۰۱۱۰۱۱ و هد روی صفر دوم قرار گرفته(از چپ بشمارید).اکنون قسمتی سمت راست هد و قسمتی سمت چپ آن قرار دارد.

حال که هد وسط است یک نشانه برای شروع قسمت سمت راست انتخاب می کند تا گمش نکند! اگر شروع ۰ باشد ۲ اگر یک باشد ۳ قرار می دهد و آن قدر سمت راست می رود که برسد به تهش و یک دونه بر میگرده عقب تا روی هیچی نباشه!(منظورم اینه که میره ته قسمت سمت راست). یعنی برای مثالی که زدیم داریم ۰۱۱۲۱۱ و هد هم روی یک چهارم قرار گرفته حالا وارد قسمت دو می شویم.

قسمت دو ( q5 , q6 , q7 , q8 ) : این قسمت یکی یکی تمام قسمت سمت راست را به جلو هل می دهد تا یک جای خالی برای خودش باز کند و برسد به شروع قسمت که نشانه گذاری اش کرده بود یعنی در این مثالی که زدیم می شود ۱۱_۰۱۱۲ و هد که رسید به نشانه، آن را هرچه که در اصل باید می بوده به جلو هل می دهد و جای خالی که برای خودش در وسط جور کرده x می نامد توی مثال ما اینجوری می شود ۰۱۱x011 (اینجا نشانه ۲ بود پس ۰ را به جلو هل دادیم) و هد هم روی اول قسمت سمت راست x می رود و وارد قسمت سه می شود.

قسمت سه ( q12 تا q19 ) : این قسمت مقایسه دو طرف x است! می خواهد ببیند که آیا دو طرفش عین هم هستند که در ww جای بگیرد یا نه. اگر مثلا چیزی شبیه abbbbb اول به ماشین داده بودیم با گذر از مرحله های قبل شده بود ۰۱۱x111 و خب توی این مرحله گیر می افتاد! اما چون مثالی که زدیم عضو ww است پس جان سالم به در می برد.
در نهایت هم همه ی ۰و۱ ها را دوباره می کند aوb و می رود به سمت حالت پایانی!
مشاهده‌ی وب‌سایت کاربر

۰
ارسال:
  

Fardad-A پاسخ داده:

تورینگ

من فکر میکنم در سوال اشکالی هست . چون این ماشین تورینگ زبان زیر را میپذیره
[tex]\left \{ ww:w\in \left \{ a,b \right \} \right \}[/tex]

۰
ارسال:
  

professional پاسخ داده:

تورینگ

بله متوجهم که تغییر State داده شده از q0 و اجازه ی رشته ی تهی رو نداده!

سوال من مفهوم کل State Machine بود.
قسمتی که دوباره به جای ۰ و ۱ میاد و ۲و ۳ میذاره برای چی هست. کتاب خیلی گنگ گفته.

۰
ارسال:
  

javadem پاسخ داده:

تورینگ

این ماشین state های اضافه زیاد داره . خیلی راحت تر میشد انجامش داد.

۰
ارسال:
  

professional پاسخ داده:

تورینگ

خب شما حلش کنید .
برامون بفرستید
ممنون میشم

۰
ارسال:
  

javadem پاسخ داده:

RE: تورینگ

شرمنده من این ۲ روز وقت نکردم سر بزنم.
من یه ماشین کشیدم . jflap کار نمیکرد مجبور شدم با دست بکشم.
این ماشینی که شما گذشتید ۲۲ تا وضعیت داره و این ماشین ۱۴ وضعیت داره. البته بازم میشه روش کار کرد و وضعیت هاشو کمتر کرد اما عجله ای شد ببخشید. حالا اگه بعدا کشیدمش واستون میذارم. تو این ماشین در وضعیت q2 مشخص میشه که تعداد ww زوج است یا نه. اگر زوج نباشد از این وضعیت خارج نمیشود. و وضعیت q9 و q12 هم پذیرفته شدن رشته را مشخص میکنند. که تمام حروف قبل از آخرین تغییر به a , b تبدیل شده باشند. اگر نیاز هست بگید تا با رشته دلخواهتون پیمایش درخت رو نشون بدم؟


فایل‌(های) پیوست شده

ارسال:
  

fatemeh69 پاسخ داده:

RE: تورینگ

(۱۳ مرداد ۱۳۹۱ ۱۰:۰۰ ب.ظ)javadem نوشته شده توسط:  شرمنده من این ۲ روز وقت نکردم سر بزنم.
من یه ماشین کشیدم . jflap کار نمیکرد مجبور شدم با دست بکشم.
این ماشینی که شما گذشتید ۲۲ تا وضعیت داره و این ماشین ۱۴ وضعیت داره. البته بازم میشه روش کار کرد و وضعیت هاشو کمتر کرد اما عجله ای شد ببخشید. حالا اگه بعدا کشیدمش واستون میذارم. تو این ماشین در وضعیت q2 مشخص میشه که تعداد ww زوج است یا نه. اگر زوج نباشد از این وضعیت خارج نمیشود. و وضعیت q9 و q12 هم پذیرفته شدن رشته را مشخص میکنند. که تمام حروف قبل از آخرین تغییر به a , b تبدیل شده باشند. اگر نیاز هست بگید تا با رشته دلخواهتون پیمایش درخت رو نشون بدم؟

گویا باز هم مشکلاتی دارد مثلا برای پذیرش رشته ی abab در state10 گیر می افتد و پذیرش نمی کند
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

javadem پاسخ داده:

تورینگ

با عرض معذرت گویا شکلی که ضمیمه کرده بودم مشکل داشت. که اصلاح شده.
چرا فقط تشکر کردید و مشکلمو تذکر ندادید (آخه با اون مشکل جواب نمیداد) ؟

۰
ارسال: #۱۰
  

professional پاسخ داده:

تورینگ

من نرسیدم چک کنم.
تا جایی که چک کردم درست بود.
به نظرتون چرا کتاب راه رو اونقدر طولانی کرده و به جای ۰و۱ از ۲و۳ استفاده کرده؟

۰
ارسال: #۱۱
  

javadem پاسخ داده:

تورینگ

شاید به دلیل قصد آموزشی کتاب بوده که خواسته مرحله به مرحله کارهارو انجام بده که نحوه ی استفاده از نوار و وضعیت ها رو به طور کامل نشون بده.جدای از قصد آموزشی البته اون کسی هم که این پاسخ رو داده(داخل کتاب) یه آدم بوده و دلیلی نداره که راه حلش بهترین باشه. مطمئنا هیچ کس نمیتونه بگه راه حلش بهترینه. ما داخل این مباحث به جواب رسیدن برامون مهمه ، پس فرقی بین این دو جواب نیست و از نظر مجموعه ها برابرند.
راه حلی که شما فرستادید اول میاد با تغییر یکی از اول و یکی از آخر a ها و bها به ۰و۱ زوج بودن تعداد ورودی را چک میکند. بعد با تبدیل ای ۰ و ۱ ها از اول به ۲ و ۳ و رفتن به آخر و ایجاد یک فاصله بین wها یک تفاوت بین wها ایجاد میکند. اما روشی که من استفاده کردم هر دو این مراحل را در یک مرحله انجام میدهد به این صورت که aها و bها رو از اول به x و y تبدیل میکند و از آخر به ۱و۲ این کار موجب میشود که هم زوج بودن تعداد ورودی را چک کنیم هم یک تفاوت بین wها ایجاد کنیم.



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  زبان ماشین تورینگ automata01 ۹ ۶,۶۴۸ ۱۱ خرداد ۱۳۹۵ ۱۲:۰۷ ق.ظ
آخرین ارسال: automata01
  ماشین تورینگ محاسبه گر Baranmalihe ۲ ۲,۶۵۴ ۰۶ اسفند ۱۳۹۴ ۰۷:۵۹ ق.ظ
آخرین ارسال: Baranmalihe
  تصمیم پذیری علوم ۹۱ ماشین تورینگ bluebaran ۲ ۳,۵۶۴ ۱۱ بهمن ۱۳۹۳ ۰۲:۲۳ ق.ظ
آخرین ارسال: bluebaran
  توضیح در مورد ماشین تورینگ mostafa2012 ۴ ۳,۴۱۱ ۰۴ بهمن ۱۳۹۳ ۱۰:۰۹ ق.ظ
آخرین ارسال: mostafa2012
  ماشین استاندارد تورینگ-ضرب کننده و جمع کننده باینری m-kafiyan ۴ ۷,۵۴۱ ۲۶ آذر ۱۳۹۳ ۰۷:۲۳ ب.ظ
آخرین ارسال: m-kafiyan
  سوال ۵۴مهندسی کامپیوتر۹۲ تورینگ so@ ۳ ۲,۲۱۷ ۱۹ آذر ۱۳۹۳ ۱۰:۱۵ ب.ظ
آخرین ارسال: so@
  ماشین تورینگ زبان {L={www:w \in {a,b Pakniat ۴ ۲,۹۰۴ ۰۱ آبان ۱۳۹۳ ۱۱:۱۷ ق.ظ
آخرین ارسال: Pakniat
  ماشین تورینگ قطعی برای ww afshari ۱ ۲,۵۱۰ ۰۲ مهر ۱۳۹۳ ۱۱:۰۸ ق.ظ
آخرین ارسال: fatemeh69
  محاسبه اجتماع مجموعه ها با ماشین تورینگ دو نواره yuttrim20 ۱ ۱,۶۴۰ ۲۶ خرداد ۱۳۹۳ ۰۲:۱۶ ق.ظ
آخرین ارسال: Jooybari
  پیاده سازی تابع search با تورینگ yuttrim20 ۱ ۱,۰۴۶ ۲۶ خرداد ۱۳۹۳ ۰۲:۱۱ ق.ظ
آخرین ارسال: Jooybari

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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