تالار گفتمان مانشت

میشه این سوالو توضیح بدید؟

سلام
گزینه 1 درسته
چون در L1 ما فقط به تعداد 10 گام یا کمتر برای پذیرش یا رد هر رشته صبر می کینم.
هر w ای که به ماشین M می دهیم اگر قبل از ده گام متوقف شد و پذیرفته شد <M,w> عضو زبانند در غیر این صورت <M,w> عضو زبان نیستند پس عضویت یا عدم عضویت هر رشته را در زمان متناهی می توانیم تشخیص دیهم پس زبان L1 تصمیم پذیر است

در زبان L2 برای آن که بفهمیم آیا این زبان بیش از 10 عضو دارد یا نه باید رشته های مختلف را به ماشین بدهیم و ببینیم آیا این ماشین بیش از ده رشته را پذیرش می کند یا نه
اما مسئله این است که اگر ما اولین w را گه دادیم ، ماشین سر این ورودی هالت نکند ما هم هیچ گاه نمی فهمیم که ماشین هالت نکرده و نمی توانیم به سراعغ رشته ی بعدی برویم و در مورد این که آیا این ماشین بیش از ده رشته را می پذیرد یا نه نظر بدهیم پس اگر وقت ی ما داریم به ماشین رشته های مختلف را می دهیم در همان 10 رشته ی اول هالت کرد ما می توانیم بگوییم <M> عضو L2 است اما اگر ماشین بر سر حداقل یکی از ورودی ها هالت نکنه دیگه نمی تونیم بگیم عضو L2 هست یا نه.
پس این زبان تصمیم پذیر نیست.

در زبان L3 ما باید تمام رشته های به طول 10 را به ماشین بدهیم و ببینم آیا همه را می پذیرد یا نه.
اگر همه ی رشته های 10 کاراکتری عضو زبان ماشین باشند پس ماشین بر سر تمام آن ها هالت می کند و چون تعداد رشته های ده کاراکتری محدوده پس تشخیص این که <M> عضو L3 است را می تونیم در زمان متناهی تشخیص دهیم . اما اگر حداقل یکی از رشته های ده کاراکتری عضو زبان ماشین نباشد و ماشین بر سر آن هالت نکند ما هم نمی توانیم روند تشخیصمان را تمام کنیم و در لوپ می افتیم پس ممکن است نتوانیم تشخیص دهیم که <M> عضو L3 است . س این زبان r.e است اما تصمیم پذیر نیست.

(11 بهمن 1393 12:36 ق.ظ)fatemeh69 نوشته شده توسط: [ -> ]سلام
گزینه ۱ درسته
چون در L1 ما فقط به تعداد ۱۰ گام یا کمتر برای پذیرش یا رد هر رشته صبر می کینم.
هر w ای که به ماشین M می دهیم اگر قبل از ده گام متوقف شد و پذیرفته شد <M,w> عضو زبانند در غیر این صورت <M,w> عضو زبان نیستند پس عضویت یا عدم عضویت هر رشته را در زمان متناهی می توانیم تشخیص دیهم پس زبان L1 تصمیم پذیر است

در زبان L2 برای آن که بفهمیم آیا این زبان بیش از ۱۰ عضو دارد یا نه باید رشته های مختلف را به ماشین بدهیم و ببینیم آیا این ماشین بیش از ده رشته را پذیرش می کند یا نه
اما مسئله این است که اگر ما اولین w را گه دادیم ، ماشین سر این ورودی هالت نکند ما هم هیچ گاه نمی فهمیم که ماشین هالت نکرده و نمی توانیم به سراعغ رشته ی بعدی برویم و در مورد این که آیا این ماشین بیش از ده رشته را می پذیرد یا نه نظر بدهیم پس اگر وقت ی ما داریم به ماشین رشته های مختلف را می دهیم در همان ۱۰ رشته ی اول هالت کرد ما می توانیم بگوییم <M> عضو L2 است اما اگر ماشین بر سر حداقل یکی از ورودی ها هالت نکنه دیگه نمی تونیم بگیم عضو L2 هست یا نه.
پس این زبان تصمیم پذیر نیست.

در زبان L3 ما باید تمام رشته های به طول ۱۰ را به ماشین بدهیم و ببینم آیا همه را می پذیرد یا نه.
اگر همه ی رشته های ۱۰ کاراکتری عضو زبان ماشین باشند پس ماشین بر سر تمام آن ها هالت می کند و چون تعداد رشته های ده کاراکتری محدوده پس تشخیص این که <M> عضو L3 است را می تونیم در زمان متناهی تشخیص دهیم . اما اگر حداقل یکی از رشته های ده کاراکتری عضو زبان ماشین نباشد و ماشین بر سر آن هالت نکند ما هم نمی توانیم روند تشخیصمان را تمام کنیم و در لوپ می افتیم پس ممکن است نتوانیم تشخیص دهیم که <M> عضو L3 است . س این زبان r.e است اما تصمیم پذیر نیست.

مر30 عزیزم