با سلام
دوتا سوال دارم
اول: اینکه کدوم ماشین از سوال یک درسته و اشتباه استنباطم کجاست؟
دوم: این مثال لینزه و من با مشکل مواجه شدم. در خود تصویر توضیح دادم اشکالم کجاست؟
متشکرم
در مورد مثال ۷-۹ اشکال شما وارد هست و به جای L باید R بگذاره
در مورد سوال اول به نظر میاد از لحاظ نحوی ماشین تورینگتون رو کلا اشتباه رسم کردید، همیشه باید ۳ چیز روی یالهای ماشین مشخص بشه
۱) حرفی که میخونیم
۲) علامتی که باید به جای آن روی نوار بنویسیم
۳) جهت حرکت هد
و اما در مورد هم ارزی:
چیزی که نوشتید درسته یعنی
[tex](a|b)*\equiv (a b)*[/tex]
اما عملگر استار یعنی ضرب پرانتز هر چند بار که نیاز باشه در خودش یعنی میتونیم رشته bba را از استار بالا ایجاد کرد ماشین تورینگ دوم درسته در صورتیکه یال آخری به جای لامبدا باید از blank یا علامت مربع استفاده کنید یعنی وقتی روی نوار به خانه خالی رسید به وضعیت نهایی برود
ماشین تورینگ اول هم زبان زیر رو می پذیرد:
[tex]a*ab*[/tex]
(۱۲ دى ۱۳۹۰ ۱۱:۱۷ ب.ظ)lsamimi نوشته شده توسط: در مورد سوال اول به نظر میاد از لحاظ نحوی ماشین تورینگتون رو کلا اشتباه رسم کردید
دوست خوبم، جهت راحتی کار اینطوری نوشتم وگرنه حرف شما صحیحه...
(۱۲ دى ۱۳۹۰ ۱۱:۱۷ ب.ظ)lsamimi نوشته شده توسط: ماشین تورینگ دوم درسته در صورتیکه یال آخری به جای لامبدا باید از blank یا علامت مربع استفاده کنید یعنی وقتی روی نوار به خانه خالی رسید به وضعیت نهایی برود
به نظرم لاندا و بلنک و مربع یه مفهومی داشته باشه! اینطور نیست؟ اگه نه چه تفاوتی با هم دارند؟
متشکرم از جوابتون
(۱۲ دى ۱۳۹۰ ۱۱:۱۷ ب.ظ)lsamimi نوشته شده توسط: اما عملگر استار یعنی ضرب پرانتز هر چند بار که نیاز باشه در خودش یعنی میتونیم رشته bba را از استار بالا ایجاد کرد ماشین تورینگ دوم درسته در صورتیکه یال آخری به جای لامبدا باید از blank یا علامت مربع استفاده کنید یعنی وقتی روی نوار به خانه خالی رسید به وضعیت نهایی برود
پس یعنی ترتیب a,b و b,a مهم نیست؟
مثلا bbaa و abb رو می شه از رابطه بالا بدست آورد؟ نباید حتما a قبل از b باشه؟
تفاوت جای خالی و blank با لامبدا در این هست که لامبدا یک رشته به طول صفر است یعنی عملا چیزی از ورودی خوانده نمی شود ولی blank طول یک دارد
البته در ماشین تورینگ شاید درست باشد که لامبدا را به جای blank به کار ببریم ولی در ماشین پشته ای لامبدا مفهوم دیگری دارد
(۱۲ دى ۱۳۹۰ ۱۱:۵۹ ب.ظ)پشتکار نوشته شده توسط:
(۱۲ دى ۱۳۹۰ ۱۱:۱۷ ب.ظ)lsamimi نوشته شده توسط: اما عملگر استار یعنی ضرب پرانتز هر چند بار که نیاز باشه در خودش یعنی میتونیم رشته bba را از استار بالا ایجاد کرد ماشین تورینگ دوم درسته در صورتیکه یال آخری به جای لامبدا باید از blank یا علامت مربع استفاده کنید یعنی وقتی روی نوار به خانه خالی رسید به وضعیت نهایی برود
پس یعنی ترتیب a,b و b,a مهم نیست؟
مثلا bbaa و abb رو می شه از رابطه بالا بدست آورد؟ نباید حتما a قبل از b باشه؟
در مورد استار باید بگویم که خیر تفاوتی در ترتیب a و b نیست برای مثال برای ساختن ba بصورت زیر می نویسیم:
[tex](a b)*\rightarrow (a b)(a b)[/tex]
حالا از پرانتز اول b و از پرانتز دوم a را انتخاب می کنیم و جمله ba بوجود می آید
در مورد سوال دوم
که رشته هاییو پذیرش میکنه که با a شروع میشن.
و تمرین ۲ همون بخشه. با دو state و فقط شناسایی حرف a قابل ترسیمه و دیگه نیازی نیست که b هم چک بشه. و میره به فاینال.