سلام
جواب این سوال به نظرم گزینه ۱ هستش ولی همه جا گزینه ۳ رو انتخاب کردن و توضیحات هم غلط غلوط دادند
من می دونم که زبانی که بازگشتی شمارا باشه مکملش بازگشتی شمارا نیست.
حالا اگه اشتباه می کنم بهم بگید.
متشکرم
(۲۲ آذر ۱۳۹۰ ۰۹:۳۷ ب.ظ)پشتکار نوشته شده توسط: سلامسلام.
جواب این سوال به نظرم گزینه ۱ هستش ولی همه جا گزینه ۳ رو انتخاب کردن و توضیحات هم غلط غلوط دادند
من می دونم که زبانی که بازگشتی شمارا باشه مکملش بازگشتی شمارا نیست.
حالا اگه اشتباه می کنم بهم بگید.
متشکرم
یک قضیه هست:زبانی وجود دارد که خودش RE باشد ولی مکمل آنRE نباشد(در واقع تحت مکمل بسته نیست).
اگر زبان Lومکمل آن هر دو RE باشدآن گاه هر دو بازگشتی نیز هستند.اگرL بازگشتی باشد آن گاه مکمل آن نیز بازگشتی است وبنابراین هردو RE نیز هستند.
امیدوارم مشکلتون حل شده باشه.
سلام دوست عزیز
چرا اینقدر قضیه رو بپیچونیم؟
وقتی گفته برای تمام رشته های L متوقف بشه، یعنی صحبتی از رشته های غیر L نکرده.
پس زبان L میشه تشخیص پذیر یا به عبارتی بازگشتی شمارا
خب تا اینجا مسئله حله
چون L بازگشتی شماراست، و با توجه به اینکه مکمل L نمی تونه بازگشتی شمارا باشه پس گزینه یک صحیحه.
حالا این قضیه ای هم که شما گفتید درسته:
اگر زبان Lومکمل آن هر دو RE باشدآن گاه هر دو R نیز هستند.اگرL بازگشتی باشد آن گاه مکمل آن نیز بازگشتی است وبنابراین هردو RE نیز هستند.
اما یه بحث مهم:
ما می دونیم L یک RE است. اما نمی دونیم مکملشم RE هست یا نه!!!؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟
(۲۲ آذر ۱۳۹۰ ۰۹:۳۷ ب.ظ)پشتکار نوشته شده توسط: سلام
جواب این سوال به نظرم گزینه ۱ هستش ولی همه جا گزینه ۳ رو انتخاب کردن و توضیحات هم غلط غلوط دادند
من می دونم که زبانی که بازگشتی شمارا باشه مکملش بازگشتی شمارا نیست.
حالا اگه اشتباه می کنم بهم بگید.
متشکرم
به نظر من چون گفته برای تمام رشته های L ماشین تورینگ متوقف می شود پس L زبان بازگشتی است یعنی R . چون زبانهای بازگشتی زیرمجموعه زبانهای بازگشتی شمارش پذیر است پس زبان L و مکمل L عضوی از زبانهای بازگشتی شمارش پذیر هستند و گزینه ۳ درست است.
(۲۳ آذر ۱۳۹۰ ۰۲:۴۹ ق.ظ)najme60 نوشته شده توسط:من هم دقیقا موافقم.(22 آذر ۱۳۹۰ ۰۹:۳۷ ب.ظ)پشتکار نوشته شده توسط: سلام
جواب این سوال به نظرم گزینه ۱ هستش ولی همه جا گزینه ۳ رو انتخاب کردن و توضیحات هم غلط غلوط دادند
من می دونم که زبانی که بازگشتی شمارا باشه مکملش بازگشتی شمارا نیست.
حالا اگه اشتباه می کنم بهم بگید.
متشکرم
به نظر من چون گفته برای تمام رشته های L ماشین تورینگ متوقف می شود پس L زبان بازگشتی است یعنی R . چون زبانهای بازگشتی زیرمجموعه زبانهای بازگشتی شمارش پذیر است پس زبان L و مکمل L عضوی از زبانهای بازگشتی شمارش پذیر هستند و گزینه ۳ درست است.
بچه‌ها من شک کردم.
ببینید این جمله من درسته؟
اگر ماشین تورینگی برای تمامی رشته‌ها متوقف شود ماشین بازگشتی است.
اگر ماشین تورینگی برای تمامی رشته‌ها متعلق به زبان L متوقف شود ماشین بازگشتی شمارا است.
اول بگید این جملات من درسته یا غلط؟
من ار کتاب صفایی اینو خوندم
(۲۳ آذر ۱۳۹۰ ۰۸:۵۶ ب.ظ)پشتکار نوشته شده توسط: بچه‌ها من شک کردم.
ببینید این جمله من درسته؟
اگر ماشین تورینگی برای تمامی رشته‌ها متوقف شود ماشین بازگشتی است.
اگر ماشین تورینگی برای تمامی رشته‌ها متعلق به زبان L متوقف شود ماشین بازگشتی شمارا است.
اول بگید این جملات من درسته یا غلط؟
من ار کتاب صفایی اینو خوندم
جملات شما درست نیست. زبان L را بازگشتی شمارا می گوییم که اگر ماشین تورینگی وجود داشته باشد که آنرا بپذیرد. حالا اگر رشته ای عضوی از L نباشد این تعریف چیزی در مورد عدم عضویت به ما نمی گوید ممکن است در یک حلقه گیر کند و هرگز متوقف نشود یا اینکه در یک وضعیت غیر پایانی قرار بگیرد. زبان L را بازگشتی می گوییم که اگر ماشین تورینگ برای تمامی رشته های متعلق به زبان L متوقف شود به عبارتی دیگر الگوریتم عضویت برای آن وجود داشته باشد.
(۲۴ آذر ۱۳۹۰ ۰۲:۵۰ ق.ظ)najme60 نوشته شده توسط: [quote='پشتکار' pid='58704' dateline='1323879973']
جملات شما درست نیست.
من نمی فهمم
این چیزی که شما نوشتید با من نوشتم چه فرقی داره؟؟؟
به نظرم فایل اتچ شده رو ببینید شاید منظورمو متوجه بشید.
شایدم هنوز من دارم اشتباه می کنم.
میشه شما هم منابعتون رو بگید؟
ببخشید حق با شما است. اگر ماشین تورینگی برای تمامی رشته‌ها متوقف شود ماشین بازگشتی است. اگر ماشین تورینگی برای تمامی رشته‌ها متعلق به زبان L متوقف شود ماشین بازگشتی شمارش پذیر است. پس در سوال زبان L بازگشتی شمارش پذیر است ولی به نظر من این زبان می تواند بازگشتی هم باشد زیرا که ماشین بازگشتی هم می تواند این زبان را بپذیرد و طبق قضیه که داریم اگر زبان L و متمم آن بازگشتی شمارش پذیر باشد آنگاه هر دو زبان بازگشتی است. حالا چون L هم بازگشتی و هم بازگشتی شمارش پذیر است پس متمم L بازگشتی شمارش پذیر است. من از روی نظریه پیتر لینز ترجمه صراف زاده می خونم.
(۲۵ آذر ۱۳۹۰ ۰۴:۱۶ ق.ظ)najme60 نوشته شده توسط: ولی به نظر من این زبان می تواند بازگشتی هم باشد زیرا که ماشین بازگشتی هم می تواند این زبان را بپذیرد
از کجا استنباط کردید؟
صورت سوال هیچ اطلاعاتی رو در این زمینه نداده که بشه استنباط کرد که زبان L بازگشتی هم می تونه باشه!
پس تا اینجا صد در صد گزینه یک صحیحه
دقت کنید!:
هر زبان بازگشتی زیر مجموعه زبان بازگشتی شمارش پذیر است ولی عکس آن صحیح نیست.
(۲۵ آذر ۱۳۹۰ ۰۴:۱۶ ق.ظ)najme60 نوشته شده توسط: طبق قضیه که داریم اگر زبان L و متمم آن بازگشتی شمارش پذیر باشد آنگاه هر دو زبان بازگشتی است. حالا چون L هم بازگشتی و هم بازگشتی شمارش پذیر است پس متمم L بازگشتی شمارش پذیر است. من از روی نظریه پیتر لینز ترجمه صراف زاده می خونم.
آیا در صورت سوال گفته که مکمل این زبان هم بازگشتی شمارش پذیره؟ نه
پس صد در صد گزینه یک صحیحه و سازمان سنجش اشتباها گزینه سه رو صحیح دونسته
اگه بازم استدلالی جهت رد صحبتهای من داشته باشید بگید.
چون احتمال ۱% هم می دم که دارم اشتباه می کنم
(۲۵ آذر ۱۳۹۰ ۰۴:۰۶ ب.ظ)پشتکار نوشته شده توسط:طبق استدلالی که شما برای سوال دارید به نظر من اصلا گزینه صحیحی نداریم.چون گزینه های ۱و۲و۳ هر کدام به نوعی درست هستند چون طبق تعریف وقتی Lعضو زبان بازگشتی شمارش پذیر باشد بدین معنی است که برای همه رشته های L ماشین تورینگی وجود دارد که همه رشته های مورد نظر را بپذیرد ومتوقف شودواین در همه گزینه‌ها صدق میکند پس ما باید از دید دیگری به سوال نگاه کنیم.در واقع باید گزینه‌ها را مرد استلال قرار دهیم تا ببینیم کدام درست‌تر است وما را به جواب درستی میرساند.(25 آذر ۱۳۹۰ ۰۴:۱۶ ق.ظ)najme60 نوشته شده توسط: ولی به نظر من این زبان می تواند بازگشتی هم باشد زیرا که ماشین بازگشتی هم می تواند این زبان را بپذیرد
از کجا استنباط کردید؟
صورت سوال هیچ اطلاعاتی رو در این زمینه نداده که بشه استنباط کرد که زبان L بازگشتی هم می تونه باشه!
پس تا اینجا صد در صد گزینه یک صحیحه
دقت کنید!:
هر زبان بازگشتی زیر مجموعه زبان بازگشتی شمارش پذیر است ولی عکس آن صحیح نیست.
(۲۵ آذر ۱۳۹۰ ۰۴:۱۶ ق.ظ)najme60 نوشته شده توسط: طبق قضیه که داریم اگر زبان L و متمم آن بازگشتی شمارش پذیر باشد آنگاه هر دو زبان بازگشتی است. حالا چون L هم بازگشتی و هم بازگشتی شمارش پذیر است پس متمم L بازگشتی شمارش پذیر است. من از روی نظریه پیتر لینز ترجمه صراف زاده می خونم.
آیا در صورت سوال گفته که مکمل این زبان هم بازگشتی شمارش پذیره؟ نه
پس صد در صد گزینه یک صحیحه و سازمان سنجش اشتباها گزینه سه رو صحیح دونسته
اگه بازم استدلالی جهت رد صحبتهای من داشته باشید بگید.
چون احتمال ۱% هم می دم که دارم اشتباه می کنم
باید دقت کرد که منظور از زبانهایی که برروی تمامی رشته های ورودی متوقف شونداینست که زبان مورد نظر یک زبان بازگشتی است.از طرفی اگر یک زبان و متمم آن هر دوبازگشتی شمارش پذیر باشند آنگاه آن زبان یک زبان بازگشتی است.
(۲۵ آذر ۱۳۹۰ ۰۷:۵۸ ب.ظ)matina نوشته شده توسط: طبق استدلالی که شما برای سوال دارید به نظر من اصلا گزینه صحیحی نداریم.چون گزینه های ۱و۲و۳ هر کدام به نوعی درست هستند
خب مهم اینه که شما تایید کنید که من اشتباه نکردم و در این زمینه اتفاق نظر داشته باشیم.
با توجه به صحبتهای ارائه شده می تونیم نتیجه بگیریم که احتمالا یا طراح سوال در طراحی سوال دقت نکردند یا مسئله چاپی داشته
حالا گزینه ۱و۲ صحیحند پس بهتر بود گزینه ۴ بجای هیچکدام می شد موارد اول و دوم
گزینه ۳ هم به تنهایی صحیحه. تنها در صورتیکه صورت سوال این مفهوم رو به ما می رسوند که ماشین بازگشتیه.
خب امیدوارم دیگه مسئله ای نباشه.
اگر شما هم موافقید
می تونیم نتیجه بگیریم این هم یکی از ایرادات طراحان سوال است
سلام دوستان من زیاد این مطلالب رو نخوندم پس استدلالم میتونه درست نباشه
به نظر من چون در سوال گفته ماشین تورینگ برای تمام رشته های L متوقف بشه( تا اینجا می تونه L بازشتی و بازگشتی شمارش پذیر باشه یعنی اگه برای رشته های L در حالت نهایی متوقف بشه L شمارش پذیر بازگشتیه و اگه در حالت های دیگری از ماشین متوقف بشه L بازگشتی اه )امادر گزینه‌ها فقط L رو عضوی از بازگشتی شمارش پذیر دونسته و این حالت زمانی می تونه درست باشه که متمم L هم عضو بازگشتی شمارش پذیر باشه( استدلال آخرم بر طبق این قضیه بوده
اگر زبان L و متمم L هر دو شمارش پذیر بازگشتی باشند آنگاه هر دو زبان بازگشتی هستند( یعنی برای L می تونه ماشین تورینگی وجود داشته باشه که برای همه‌ی رشنته هاش متوقف بشه))
دوستان لطفا نظراتتون رو در مورد استدلالم بگین
من فکر کنم مشکل این سوال اشتباه جمله بندی سوال هست.در نگاه اول که سوال رو می خونی وقتی گفته می شه " برای تمام رشته های L" چون دقیقا نگفته "برای تمام رشته های متعلق به L" بصورت پیش فرض بازگشتی در نظر گرفته می شه .و طبق همون قضیه که دوستان گفتند جواب گزینه سه میشه.
از یه طرف دیگه هم میشه فهمید که منظور زبان بازگشتی چون اگر منظور زبان بازگشتی برشمردنی بود تمام گزینه‌ها درست می شد به جز هیچکدام!
توی یه همچین سوالایی فکر کنم باید یه مقدار با سوال کشتی گرفت و تجزیه تحلیل کرد چون فکر نکنم یه همچین سوالایی رو سنجش حذف کنه (کما اینکه این کار رو برای این سوال نکرده) و بهتره که امتیازش رو از دست ندیم.
ولی با توجه به جوابی که سنجش داده بعید می دونم خودشون هم بدونن سوال چی بوده .کل لینز رو تو یه خط نقض کرده.صد رحمت به پارسه.
(۲۶ آذر ۱۳۹۰ ۰۹:۰۶ ب.ظ)rezatotti نوشته شده توسط: من فکر کنم مشکل این سوال اشتباه جمله بندی سوال هست.در نگاه اول که سوال رو می خونی وقتی گفته می شه " برای تمام رشته های L" چون دقیقا نگفته "برای تمام رشته های متعلق به L" بصورت پیش فرض بازگشتی در نظر گرفته می شه .و طبق همون قضیه که دوستان گفتند جواب گزینه سه میشه.
دوست خوبم، صورت سوال وقتی می گه زبان L مفروض است، منظورشم از تمامی رشته های L همان L مفروضه که همون بازگشتی شمارا می شه.
(۲۶ آذر ۱۳۹۰ ۰۹:۰۶ ب.ظ)rezatotti نوشته شده توسط: از یه طرف دیگه هم میشه فهمید که منظور زبان بازگشتی چون اگر منظور زبان بازگشتی برشمردنی بود تمام گزینه‌ها درست می شد به جز هیچکدام!اگر منظور زبان بازگشتی برشمردنی بود تمام گزینه‌ها بغیر از گزینه ۳ و ۴ درست می شد