صفحه ۳۱۱ لینز ترجمه صراف زاده(ابتدای فصل ۱۱ دسته بندی زبانهای صوری و آتاماتا) نوشته که:
غالب بحث های این فصل در مورد زبانهایی صحت دارد که حاوی رشته تهی نباشند.ماشین های تورینگ به گونه ای که تعریف شده اند نمی توانند رشته تهی را بپذیرند.
ایا این موضوع کلیت داره؟
از طرفی سوال ۱۲۲ علوم کامپیوتر ۸۹ رو که از کتاب مقسمی میخوندم به همین نکته اشاره کرده بود و مسئله رو حل کرده بود!!!
فرض کنید زبان L شامل رشته تهی هم باشه.تو همون حالت اول میشه گفت اگه blank دیدی برو به یه حالت پذیرش.پس رشته تهی پذیرفته میشه.معمولا گفته میشه که ماشین تورینگ با رشته تهی در بعضی از زبان‌ها و محاسبات مشکل داره ولی این به این معنی نیست که این ماشین نمیتونه رشته تهی رو پذیرش کنه.
اما در تمرینات بخش۹-۱ سوال ۷ قسمت f توی حل تمرین هم گفته که TM نباید رشته لاندا را بپذیرد!!!!!!
(۰۷ دى ۱۳۹۰ ۱۱:۴۷ ب.ظ)NoOne نوشته شده توسط: اما در تمرینات بخش۹-۱ سوال ۷ قسمت f توی حل تمرین هم گفته که TM نباید رشته لاندا را بپذیرد!!!!!!این که تو اون سوال گفته نباید بپذیره به این معنی نیست که در حالت کلی ماشین تورینگ تهی نمی پذیره
ماشین تورینگ استاندارد رشته لاندا رو پذیرش نمیکنه، اما با تغییرات جزئی، میشه کاری کرد که پذیرش کنه.
فرضا یه حالت اینه که، در ماشین تورینگ قید کنیم که هد در آغاز، در ابتدای رشته قرار میگیره
در این صورت اگر در ابتدا blank دید یعنی رشته تهی بوده.
یه حالت دیگه اینه که رشته بین دو علامت محصور باشه حتما
که اگر ماشین بعد از جستجو به کاراکتری برخورد نکرد یعنی تهی بوده و .....
ماشین تورینگ طبق تعریف هر نوع زبانی رو می‌پذیره. رشته تهی رو هم به سادگی می‌تونه بپذیره. برخی مباحث که مربوط به رشته لامبدا هست رو با این سوال قاطی نکنید.
طبق تعریف هر رشته با یه علامت مشخصه رشته شروع میشه و رشته تهی هم می‌تونه با یه علامت شبیه < شروع بشه و بعدش یه blank باشه. هد هم همیشه در ابتدای رشته قرار داره.
رشته لامبدا مگه همون رشته تهی نیست؟