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

آیا ماشین تورینگ نمی تواند رشته تهی را بپذیرد؟!!

ارسال:
  

Msccom پرسیده:

آیا ماشین تورینگ نمی تواند رشته تهی را بپذیرد؟!!

صفحه ۳۱۱ لینز ترجمه صراف زاده(ابتدای فصل ۱۱ دسته بندی زبانهای صوری و آتاماتا) نوشته که:
غالب بحث های این فصل در مورد زبانهایی صحت دارد که حاوی رشته تهی نباشند.ماشین های تورینگ به گونه ای که تعریف شده اند نمی توانند رشته تهی را بپذیرند.

ایا این موضوع کلیت داره؟

از طرفی سوال ۱۲۲ علوم کامپیوتر ۸۹ رو که از کتاب مقسمی میخوندم به همین نکته اشاره کرده بود و مسئله رو حل کرده بود!!!

۰
ارسال:
  

mfXpert پاسخ داده:

آیا ماشین تورینگ نمی تواند رشته تهی را بپذیرد؟!!

فرض کنید زبان L شامل رشته تهی هم باشه.تو همون حالت اول میشه گفت اگه blank دیدی برو به یه حالت پذیرش.پس رشته تهی پذیرفته میشه.معمولا گفته میشه که ماشین تورینگ با رشته تهی در بعضی از زبان‌ها و محاسبات مشکل داره ولی این به این معنی نیست که این ماشین نمیتونه رشته تهی رو پذیرش کنه.

۰
ارسال:
  

admin پاسخ داده:

آیا ماشین تورینگ نمی تواند رشته تهی را بپذیرد؟!!

ماشین تورینگ طبق تعریف هر نوع زبانی رو می‌پذیره. رشته تهی رو هم به سادگی می‌تونه بپذیره. برخی مباحث که مربوط به رشته لامبدا هست رو با این سوال قاطی نکنید.
طبق تعریف هر رشته با یه علامت مشخصه رشته شروع می‌شه و رشته تهی هم می‌تونه با یه علامت شبیه < شروع بشه و بعدش یه blank باشه. هد هم همیشه در ابتدای رشته قرار داره.

۰
ارسال:
  

Msccom پاسخ داده:

آیا ماشین تورینگ نمی تواند رشته تهی را بپذیرد؟!!

اما در تمرینات بخش۹-۱ سوال ۷ قسمت f توی حل تمرین هم گفته که TM نباید رشته لاندا را بپذیرد!!!!!!

۰
ارسال:
  

mfXpert پاسخ داده:

آیا ماشین تورینگ نمی تواند رشته تهی را بپذیرد؟!!

(۰۷ دى ۱۳۹۰ ۱۱:۴۷ ب.ظ)NoOne نوشته شده توسط:  اما در تمرینات بخش۹-۱ سوال ۷ قسمت f توی حل تمرین هم گفته که TM نباید رشته لاندا را بپذیرد!!!!!!
این که تو اون سوال گفته نباید بپذیره به این معنی نیست که در حالت کلی ماشین تورینگ تهی نمی پذیره

۰
ارسال:
  

reyhaneh64 پاسخ داده:

RE: آیا ماشین تورینگ نمی تواند رشته تهی را بپذیرد؟!!

ماشین تورینگ استاندارد رشته لاندا رو پذیرش نمیکنه، اما با تغییرات جزئی‌، میشه کاری کرد که پذیرش کنه.
فرضا یه حالت اینه که‌، در ماشین تورینگ قید کنیم که هد در آغاز‌، در ابتدای رشته قرار میگیره
در این صورت اگر در ابتدا blank دید یعنی رشته تهی بوده.
یه حالت دیگه اینه که رشته بین دو علامت محصور باشه حتما
که اگر ماشین بعد از جستجو به کاراکتری برخورد نکرد یعنی تهی بوده و .....

۰
ارسال:
  

Msccom پاسخ داده:

آیا ماشین تورینگ نمی تواند رشته تهی را بپذیرد؟!!

رشته لامبدا مگه همون رشته تهی نیست؟



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  RE برای زبان منظم "تمام رشته هایی که حداقل شامل ۲ رشته ۰۰ باشند" reza6966 ۲ ۹۳۸ ۰۹ مهر ۱۳۹۲ ۰۲:۳۱ ق.ظ
آخرین ارسال: black_knight
  گرامر برای رشته هایی از a و b که رشته به دو زیر رشته مشابه قابل تقسیم نباشد sajad2010 ۱ ۸۱۶ ۰۴ دى ۱۳۹۱ ۰۱:۰۲ ق.ظ
آخرین ارسال: Jooybari
  رسم dfa برای رشته هایی که سومین سمبل از انتهای رشته ۱ باشد Neda_H ۱۰ ۲,۷۹۲ ۱۲ فروردین ۱۳۹۱ ۰۲:۵۸ ب.ظ
آخرین ارسال: لهمشد
  زبان تهی ومکمل آن Msccom ۵ ۱,۴۲۰ ۲۱ دى ۱۳۹۰ ۱۰:۴۹ ق.ظ
آخرین ارسال: sasanlive
  نحوه رسم تورینگ f.b ۳ ۱,۵۳۷ ۱۵ دى ۱۳۹۰ ۰۱:۳۴ ق.ظ
آخرین ارسال: ف.ش
  ماشین پشته ای معین و نامعین f.b ۱ ۳,۴۹۷ ۱۴ دى ۱۳۹۰ ۰۱:۳۴ ب.ظ
آخرین ارسال: homa

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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