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

سوال ۱۲۰ علوم کامپیوتر ۹۴

ارسال:
  

Iranian Wizard پرسیده:

سوال ۱۲۰ علوم کامپیوتر ۹۴

سلام.
ماشین تورینگ غیر قطعی M که برای هر ورودی نهایتا متوقف می شود با زبان L مفروض است.
همه گزینه های زیر صحیح هستند،بجز:

۱-اگر [tex]x\notin L[/tex] لزوما ماشین در هر محاسبه پاسخ خیر (No) می دهد.
۲-لزوما متمم L (زبان [tex]L'[/tex]) دارای یک ماشین تورینگ قطعی است که برای هر ورودی متوقف می شود.
۳-لزوما L دارای یک ماشین تورینگ قطعی است که برای هر ورودی متوقف می شود.
۴-اگر برای ورودی x ماشین پاسخ خیر (No) بدهد لزوما [tex]x\notin L[/tex] .

با تشکر.
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

alireza01 پاسخ داده:

RE: سوال ۱۲۰ علوم کامپیوتر ۹۴

(۱۵ اسفند ۱۳۹۴ ۰۹:۱۶ ب.ظ)Iranian Wizard نوشته شده توسط:  سلام.
ماشین تورینگ غیر قطعی M که برای هر ورودی نهایتا متوقف می شود با زبان L مفروض است
همه گزینه های زیر صحیح هستند،بجز:

۱-اگر [tex]x\notin L[/tex] لزوما ماشین در هر محاسبه پاسخ خیر (No) می دهد.
۲-لزوما متمم L (زبان [tex]L'[/tex]) دارای یک ماشین تورینگ قطعی است که برای هر ورودی متوقف می شود.
۳-لزوما L دارای یک ماشین تورینگ قطعی است که برای هر ورودی متوقف می شود.
۴-اگر برای ورودی x ماشین پاسخ خیر (No) بدهد لزوما [tex]x\notin L[/tex] .

با تشکر.

قضیه : برای هر ماشین تورینگ غیر قطعی ، ماشین تورینگ با حالت قطعی برای آن وجود دارد
توضیح : طبق صورت سوال ماشین تورینگ در این سوال برای هر ورودی متوقف میشود ( یا Yes یا No )، این تعریف ما رو یاد زبان های بازگشتی یا REC میندازه که هر ورودی بهش بدیهم توقف میکنه، زبان L هم داریم که اگه به ماشین بدیم حتما Yes رو میده به ما
پس برای اینکه ماشین تورینگ پاسخ Yes به ما بده ورودی باید subset L باشه این توصیفات بریم سراغ گزینه ها.
میشه شکل زیر :



گزینه ۱) اگر [tex]x\notin L[/tex] صد رد صد ماشین به ما پاسخ No میده ( قسمت آبی رنگ ) ( درست )
گزینه ۲ ) زبان های REC تحت عمل مکمل گیری بسته هستند .
گزینه ۳ ) قضیه ای که گفتم ( درست )
گزینه ۴ ) اگر ورودی ماشین x باشه ، و ماشین No به ما بدهد صد در صد نمیشه گفت [tex]x\notin L[/tex] . ممکنه عضو L هم باشه ( قسمتی که زردش یکم تیره تره ) ( غلط )

پاسخ تست : گزینه ۴
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  جزوه برای درس نظریه علوم کامپیوتر matias ۱۳ ۱۵,۱۱۳ ۲۴ شهریور ۱۴۰۳ ۰۸:۳۳ ب.ظ
آخرین ارسال: shabankhah
  گرایش های علوم کامپیوتر alisaaa ۴ ۴,۳۲۱ ۱۳ آذر ۱۴۰۲ ۰۴:۲۷ ب.ظ
آخرین ارسال: hashemhamidi
  علوم کامپیوتر شریف یا نرم افزار تهران؟ ۴L1R3Z4 ۴۴ ۳۲,۸۵۱ ۰۶ شهریور ۱۴۰۲ ۰۸:۱۲ ب.ظ
آخرین ارسال: moeinbahari
  رتبه ۵۴ علوم کامپیوتر و ۷۶ ریاضی ارشد ۱۴۰۰ Computer92 ۰ ۲,۳۵۶ ۰۸ شهریور ۱۴۰۰ ۰۹:۴۶ ب.ظ
آخرین ارسال: Computer92
  سوال ۸ دکتری علوم کامپیوتر سال ۹۴ ss311 ۲ ۳,۴۹۰ ۲۶ اردیبهشت ۱۳۹۹ ۱۲:۳۷ ب.ظ
آخرین ارسال: ss311
  سوال ۱۴ علوم کامپیوتر ۹۶ ss311 ۴ ۳,۸۲۸ ۲۶ اردیبهشت ۱۳۹۹ ۱۲:۳۳ ب.ظ
آخرین ارسال: ss311
  جایگشت( ارشد علوم کامپیوتر ۹۸ ) ss311 ۰ ۱,۹۱۴ ۰۳ اسفند ۱۳۹۸ ۱۲:۴۵ ب.ظ
آخرین ارسال: ss311
  رنگ کردن رئوس گراف( ارشد علوم کامپیوتر ۹۸ ) ss311 ۰ ۲,۱۲۶ ۰۳ اسفند ۱۳۹۸ ۱۲:۴۳ ب.ظ
آخرین ارسال: ss311
  سوال ۳ دکتری علوم کامپیوتر ۹۷ ss311 ۲ ۲,۹۷۴ ۰۶ بهمن ۱۳۹۸ ۰۴:۴۵ ب.ظ
آخرین ارسال: ss311
  تغییر رشته از ریاضی به علوم کامپیوتر در ارشد Fghs ۳ ۵,۴۷۶ ۲۱ دى ۱۳۹۸ ۰۵:۱۱ ب.ظ
آخرین ارسال: parisa1140

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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