دوست خوبم بازم متذکر میشم، من هیچ ادعایی ندارم و خیلی کوچکتر از اونم که بخوام حرفی بزنم، ولی خب این مسئله برام تقریبا واضحه. ولی شما اگه بازم اشتباهی می بینید خوشحال میشم بهم بگید و منم در علمتون شریک بدونید.
حالا می پردازم به سوالات شما. (فقط خواهش می کنم اگه فایل ورد می ذارید داک بذارید نه داک ایکس متشکرم
)
نقل قول: این قضیه رو اگه خوب بخونین نتایج پایین رو ازشون میشه گرفت
۱ - if L € RE ,L’ € RE L € R , L’ € R
۲ - L € R L’ € R L € RE ,L’ € RE
از نتیجه دومم میشه برداشت کرد زمانی که ال بازگشتی باشه ال ومتممش میتونه بازگشتی شمارا باشه. (ولی شما گفتین حتما اگه ال بازگشتی شمارا باشه مکملش بازگشتی شمارا نیست) در حالیکه قضیه بالا خلاف این رو نشون داد.
میشه از نظر زبانی بگید تفاوت زبانهای بازگشتی و بازگشتی شمارا در چیه؟ بدون ماشین تورینگ بگید. مرسی
***********************************************
ببین دوست خوبم
قضایایی که آوردید درستند.
بذارید با یه سوال مطلبم رو بگم:
اگر ال مستقل از متن باشه، آیا میشه گفت که منظمم هستش؟ قطعا خیر. چرا؟ چون زبانهای منظم زیر مجموعه مستقل از متنند.
ولی ما می تونیم بگیم زبانهای منظم، مستقل از متن هم هستند.
به عبارتی اگر ال زبان منظمی بود، مستتقل از متن هم هست.
حالا اگر ال بازگشتی شمارا باشه، آیا میشه گفت که بازگشتی هم هستش؟ قطعا خیر! چرا؟ چون زبانهای بازگشتی زیر مجموعه بازگشتی شمارا هستند.
ولی ما می تونیم بگیم زبانهای بازگشتی، زبانهای بازگشتی شما را هم هستند.
در سوال گفته شده برای همه رشته های ال ماشین تورینگ متوقف بشه پس تا اینجا، ال می تونه هم بازگشتی باشه هم بازگشتی شمارا. چرا؟ چون گفته رشته های ال رو می پذیره و ما می دونیم ماشینهای بازگشتی و شمارا هم رشته های ال رو می پذیرند.
ولی مسئله اینجاست که ما در مورد تشخیص بازگشتی و بازگشتی شمارا باید کمی دقت کنیم.
باتوجه به اینکه صورت سوال چیزی در مورد رشته های غیر ال نگفته که آیا ماشین تورینگ آنها را متوقف می کنه یا نه، و چون ماشین عادی طوری است که برای رشته های متعلق اکسپت و غیر آنها را ریجکت یا لوپ می کنه، پس ال هم در این صورت سوال همین قانون رو خواهد داشت. و چنین ماشینی بازگشتی شماراست.
حالا مسئله بعد از تخیص مدل ال اینه که ببینیم جواب در کدام گزینه هست.
طراح سوال هم کلک خوبی بکار برده و همه رو نوشته ال متعلق به شماراست که تا اینجا قضیه حله ولی در مورد مکمل ال مسئله وجود داره که باید رجوع شه به صورت سوال که چون ال بازگشتی شماراست و زبانهای بازگشتی شمارا نسبت به مکمل بسته نیستند، پس گزینه یک صحیحه.
حالا احتمال کج فهمی منم وجود داره
اگه ممکنه دوستان جواب سوال ضمیمه رو بدند و بگن کدوم گزینه صحیحه؟
اینطوری فکر کنم بهتر بتونیم در مورد گزینه صحیح تصمیم بگیریم