در مورد مثال ۷-۹ اشکال شما وارد هست و به جای 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 باشه؟

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