با سلام
دوستان لطفا اگر میتونید برای من این مثال رو توضیح بدید.
این همه دوباره کاری برای چیه؟ کتاب راه حل رو توضیح داده اما خیلی گنگه!
من فکر میکنم در سوال اشکالی هست . چون این ماشین تورینگ زبان زیر را میپذیره
[tex]\left \{ ww:w\in \left \{ a,b \right \} \right \}[/tex]
بله متوجهم که تغییر State داده شده از q0 و اجازه ی رشته ی تهی رو نداده!
سوال من مفهوم کل State Machine بود.
قسمتی که دوباره به جای ۰ و ۱ میاد و ۲و ۳ میذاره برای چی هست. کتاب خیلی گنگ گفته.
برای حل سوال های ماشین تورینگ کافیه که یک مثال بزنید و آن مثال را اگر جواب دارید بیاندازید توی ماشین و ببینید چه بر سرش می آید تا ایده ماشین را بگیرید. اگر هم جواب ندارید یک ایده برایش بسازید منتهی بعد از کشیدن طراحی ایده ی تان حتما یک حالتی را جواب نیست را به طراحی بدهید تا مبادا چیز اشتباهی را بپذیرد.
اما درباره ی این سوال جواب کتاب را توضیح می دهیم:
شکل رسم شده در واقع سه قسمت اصلی داره،
قسمت یک ( q0 , q1 ,q2 ,q3 ) : این قسمت عبارتی که دارید رو به صفر یک تبدیل می کنه تا هد رو در قسمتی قرار بده که عبارت به دو قسمت مساوی تقسیم بشه (توجه تان را جلب می کنم که طول هر عبارت در ww حتما زوج است). یعنی اگر مثلا داشته باشیم abbabb آخر این قسمت داریم ۰۱۱۰۱۱ و هد روی صفر دوم قرار گرفته(از چپ بشمارید).اکنون قسمتی سمت راست هد و قسمتی سمت چپ آن قرار دارد.
حال که هد وسط است یک نشانه برای شروع قسمت سمت راست انتخاب می کند تا گمش نکند! اگر شروع ۰ باشد ۲ اگر یک باشد ۳ قرار می دهد و آن قدر سمت راست می رود که برسد به تهش و یک دونه بر میگرده عقب تا روی هیچی نباشه!(منظورم اینه که میره ته قسمت سمت راست). یعنی برای مثالی که زدیم داریم ۰۱۱۲۱۱ و هد هم روی یک چهارم قرار گرفته حالا وارد قسمت دو می شویم.
قسمت دو ( q5 , q6 , q7 , q8 ) : این قسمت یکی یکی تمام قسمت سمت راست را به جلو هل می دهد تا یک جای خالی برای خودش باز کند و برسد به شروع قسمت که نشانه گذاری اش کرده بود یعنی در این مثالی که زدیم می شود ۱۱_۰۱۱۲ و هد که رسید به نشانه، آن را هرچه که در اصل باید می بوده به جلو هل می دهد و جای خالی که برای خودش در وسط جور کرده x می نامد توی مثال ما اینجوری می شود ۰۱۱x011 (اینجا نشانه ۲ بود پس ۰ را به جلو هل دادیم) و هد هم روی اول قسمت سمت راست x می رود و وارد قسمت سه می شود.
قسمت سه ( q12 تا q19 ) : این قسمت مقایسه دو طرف x است! می خواهد ببیند که آیا دو طرفش عین هم هستند که در ww جای بگیرد یا نه. اگر مثلا چیزی شبیه abbbbb اول به ماشین داده بودیم با گذر از مرحله های قبل شده بود ۰۱۱x111 و خب توی این مرحله گیر می افتاد! اما چون مثالی که زدیم عضو ww است پس جان سالم به در می برد.
در نهایت هم همه ی ۰و۱ ها را دوباره می کند aوb و می رود به سمت حالت پایانی!
این ماشین state های اضافه زیاد داره . خیلی راحت تر میشد انجامش داد.
خب شما حلش کنید .
برامون بفرستید
ممنون میشم
شرمنده من این ۲ روز وقت نکردم سر بزنم.
من یه ماشین کشیدم . jflap کار نمیکرد مجبور شدم با دست بکشم.
این ماشینی که شما گذشتید ۲۲ تا وضعیت داره و این ماشین ۱۴ وضعیت داره. البته بازم میشه روش کار کرد و وضعیت هاشو کمتر کرد اما عجله ای شد ببخشید. حالا اگه بعدا کشیدمش واستون میذارم. تو این ماشین در وضعیت q2 مشخص میشه که تعداد ww زوج است یا نه. اگر زوج نباشد از این وضعیت خارج نمیشود. و وضعیت q9 و q12 هم پذیرفته شدن رشته را مشخص میکنند. که تمام حروف قبل از آخرین تغییر به a , b تبدیل شده باشند. اگر نیاز هست بگید تا با رشته دلخواهتون پیمایش درخت رو نشون بدم؟
با عرض معذرت گویا شکلی که ضمیمه کرده بودم مشکل داشت. که اصلاح شده.
چرا فقط تشکر کردید و مشکلمو تذکر ندادید (آخه با اون مشکل جواب نمیداد) ؟
من نرسیدم چک کنم.
تا جایی که چک کردم درست بود.
به نظرتون چرا کتاب راه رو اونقدر طولانی کرده و به جای ۰و۱ از ۲و۳ استفاده کرده؟
شاید به دلیل قصد آموزشی کتاب بوده که خواسته مرحله به مرحله کارهارو انجام بده که نحوه ی استفاده از نوار و وضعیت ها رو به طور کامل نشون بده.جدای از قصد آموزشی البته اون کسی هم که این پاسخ رو داده(داخل کتاب) یه آدم بوده و دلیلی نداره که راه حلش بهترین باشه. مطمئنا هیچ کس نمیتونه بگه راه حلش بهترینه. ما داخل این مباحث به جواب رسیدن برامون مهمه ، پس فرقی بین این دو جواب نیست و از نظر مجموعه ها برابرند.
راه حلی که شما فرستادید اول میاد با تغییر یکی از اول و یکی از آخر a ها و bها به ۰و۱ زوج بودن تعداد ورودی را چک میکند. بعد با تبدیل ای ۰ و ۱ ها از اول به ۲ و ۳ و رفتن به آخر و ایجاد یک فاصله بین wها یک تفاوت بین wها ایجاد میکند. اما روشی که من استفاده کردم هر دو این مراحل را در یک مرحله انجام میدهد به این صورت که aها و bها رو از اول به x و y تبدیل میکند و از آخر به ۱و۲ این کار موجب میشود که هم زوج بودن تعداد ورودی را چک کنیم هم یک تفاوت بین wها ایجاد کنیم.
(۱۳ مرداد ۱۳۹۱ ۱۰:۰۰ ب.ظ)javadem نوشته شده توسط: شرمنده من این ۲ روز وقت نکردم سر بزنم.
من یه ماشین کشیدم . jflap کار نمیکرد مجبور شدم با دست بکشم.
این ماشینی که شما گذشتید ۲۲ تا وضعیت داره و این ماشین ۱۴ وضعیت داره. البته بازم میشه روش کار کرد و وضعیت هاشو کمتر کرد اما عجله ای شد ببخشید. حالا اگه بعدا کشیدمش واستون میذارم. تو این ماشین در وضعیت q2 مشخص میشه که تعداد ww زوج است یا نه. اگر زوج نباشد از این وضعیت خارج نمیشود. و وضعیت q9 و q12 هم پذیرفته شدن رشته را مشخص میکنند. که تمام حروف قبل از آخرین تغییر به a , b تبدیل شده باشند. اگر نیاز هست بگید تا با رشته دلخواهتون پیمایش درخت رو نشون بدم؟
گویا باز هم مشکلاتی دارد مثلا برای پذیرش رشته ی abab در state10 گیر می افتد و پذیرش نمی کند