(۲۲ آذر ۱۳۹۰ ۰۹:۳۷ ب.ظ)پشتکار نوشته شده توسط:  سلام
جواب این سوال به نظرم گزینه ۱ هستش ولی همه جا گزینه ۳ رو انتخاب کردن و توضیحات هم غلط غلوط دادند
من می دونم که زبانی که بازگشتی شمارا باشه مکملش بازگشتی شمارا نیست.
حالا اگه اشتباه می کنم بهم بگید.
متشکرم

سلام.
یک قضیه هست:زبانی وجود دارد که خودش 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 متوقف شود به عبارتی دیگر الگوریتم عضویت برای آن وجود داشته باشد.

ببخشید حق با شما است. اگر ماشین تورینگی برای تمامی رشته‌ها متوقف شود ماشین بازگشتی است. اگر ماشین تورینگی برای تمامی رشته‌ها متعلق به زبان L متوقف شود ماشین بازگشتی شمارش پذیر است. پس در سوال زبان L بازگشتی شمارش پذیر است ولی به نظر من این زبان می تواند بازگشتی هم باشد زیرا که ماشین بازگشتی هم می تواند این زبان را بپذیرد و طبق قضیه که داریم اگر زبان L و متمم آن بازگشتی شمارش پذیر باشد آنگاه هر دو زبان بازگشتی است. حالا چون L هم بازگشتی و هم بازگشتی شمارش پذیر است پس متمم L بازگشتی شمارش پذیر است. من از روی نظریه پیتر لینز ترجمه صراف زاده می خونم.

(۲۵ آذر ۱۳۹۰ ۰۴:۱۶ ق.ظ)najme60 نوشته شده توسط:  ولی به نظر من این زبان می تواند بازگشتی هم باشد زیرا که ماشین بازگشتی هم می تواند این زبان را بپذیرد

از کجا استنباط کردید؟
صورت سوال هیچ اطلاعاتی رو در این زمینه نداده که بشه استنباط کرد که زبان L بازگشتی هم می تونه باشه!
پس تا اینجا صد در صد گزینه یک صحیحه
دقت کنید!:
هر زبان بازگشتی زیر مجموعه زبان بازگشتی شمارش پذیر است ولی عکس آن صحیح نیست.

(۲۵ آذر ۱۳۹۰ ۰۴:۱۶ ق.ظ)najme60 نوشته شده توسط:  طبق قضیه که داریم اگر زبان L و متمم آن بازگشتی شمارش پذیر باشد آنگاه هر دو زبان بازگشتی است. حالا چون L هم بازگشتی و هم بازگشتی شمارش پذیر است پس متمم L بازگشتی شمارش پذیر است. من از روی نظریه پیتر لینز ترجمه صراف زاده می خونم.

آیا در صورت سوال گفته که مکمل این زبان هم بازگشتی شمارش پذیره؟ نه


پس صد در صد گزینه یک صحیحه و سازمان سنجش اشتباها گزینه سه رو صحیح دونسته

اگه بازم استدلالی جهت رد صحبتهای من داشته باشید بگید.
چون احتمال ۱% هم می دم که دارم اشتباه می کنم

سلام دوستان من زیاد این مطلالب رو نخوندم پس استدلالم میتونه درست نباشه
به نظر من چون در سوال گفته ماشین تورینگ برای تمام رشته های L متوقف بشه( تا اینجا می تونه L بازشتی و بازگشتی شمارش پذیر باشه یعنی اگه برای رشته های L در حالت نهایی متوقف بشه L شمارش پذیر بازگشتیه و اگه در حالت های دیگری از ماشین متوقف بشه L بازگشتی اه )امادر گزینه‌ها فقط L رو عضوی از بازگشتی شمارش پذیر دونسته و این حالت زمانی می تونه درست باشه که متمم L هم عضو بازگشتی شمارش پذیر باشه( استدلال آخرم بر طبق این قضیه بوده
اگر زبان L و متمم L هر دو شمارش پذیر بازگشتی باشند آنگاه هر دو زبان بازگشتی هستند( یعنی برای L می تونه ماشین تورینگی وجود داشته باشه که برای همه‌ی رشنته هاش متوقف بشه))

دوستان لطفا نظراتتون رو در مورد استدلالم بگین

من فکر کنم مشکل این سوال اشتباه جمله بندی سوال هست.در نگاه اول که سوال رو می خونی وقتی گفته می شه " برای تمام رشته های L" چون دقیقا نگفته "برای تمام رشته های متعلق به L" بصورت پیش فرض بازگشتی در نظر گرفته می شه .و طبق همون قضیه که دوستان گفتند جواب گزینه سه میشه.
از یه طرف دیگه هم میشه فهمید که منظور زبان بازگشتی چون اگر منظور زبان بازگشتی برشمردنی بود تمام گزینه‌ها درست می شد به جز هیچکدام!
توی یه همچین سوالایی فکر کنم باید یه مقدار با سوال کشتی گرفت و تجزیه تحلیل کرد چون فکر نکنم یه همچین سوالایی رو سنجش حذف کنه (کما اینکه این کار رو برای این سوال نکرده) و بهتره که امتیازش رو از دست ندیم.
ولی با توجه به جوابی که سنجش داده بعید می دونم خودشون هم بدونن سوال چی بوده .کل لینز رو تو یه خط نقض کرده.صد رحمت به پارسه.

(۲۶ آذر ۱۳۹۰ ۰۹:۰۶ ب.ظ)rezatotti نوشته شده توسط:  من فکر کنم مشکل این سوال اشتباه جمله بندی سوال هست.در نگاه اول که سوال رو می خونی وقتی گفته می شه " برای تمام رشته های L" چون دقیقا نگفته "برای تمام رشته های متعلق به L" بصورت پیش فرض بازگشتی در نظر گرفته می شه .و طبق همون قضیه که دوستان گفتند جواب گزینه سه میشه.

دوست خوبم‌، صورت سوال وقتی می گه زبان L مفروض است، منظورشم از تمامی رشته های L همان L مفروضه که همون بازگشتی شمارا می شه.

(۲۶ آذر ۱۳۹۰ ۰۹:۰۶ ب.ظ)rezatotti نوشته شده توسط:  از یه طرف دیگه هم میشه فهمید که منظور زبان بازگشتی چون اگر منظور زبان بازگشتی برشمردنی بود تمام گزینه‌ها درست می شد به جز هیچکدام!

اگر منظور زبان بازگشتی برشمردنی بود تمام گزینه‌ها بغیر از گزینه ۳ و ۴ درست می شد

پشتکار جان من توضیح کامل و یه سری از اشتباههایی که به نظرم در پست هاتون نوشتین رو در ضمیمه میذارم امیدوارم قانعتون کنه
امیدوارم قانع بشین اگه نشدین بگین باز در موردش باهم بحث کنیم
درضمن درسته که یکسری از سوالات کنکور غلط اند ولی این دلیل نمیشه که وقتی سوالی رو غلط برداشت کردیم بگیم سوال غلطه

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

اشتباه دوستمون پشتکار جان از اینجا نشات میگیره

دوست خوبم بازم متذکر میشم، من هیچ ادعایی ندارم و خیلی کوچکتر از اونم که بخوام حرفی بزنم، ولی خب این مسئله برام تقریبا واضحه. ولی شما اگه بازم اشتباهی می بینید خوشحال میشم بهم بگید و منم در علمتون شریک بدونید.
حالا می پردازم به سوالات شما. (فقط خواهش می کنم اگه فایل ورد می ذارید داک بذارید نه داک ایکس متشکرم)

نقل قول: این قضیه رو اگه خوب بخونین نتایج پایین رو ازشون میشه گرفت
۱ - if L € RE ,L’ € RE  L € R , L’ € R
۲ - L € R  L’ € R  L € RE ,L’ € RE
از نتیجه دومم میشه برداشت کرد زمانی که ال بازگشتی باشه ال ومتممش میتونه بازگشتی شمارا باشه. (ولی شما گفتین حتما اگه ال بازگشتی شمارا باشه مکملش بازگشتی شمارا نیست) در حالیکه قضیه بالا خلاف این رو نشون داد.

میشه از نظر زبانی بگید تفاوت زبانهای بازگشتی و بازگشتی شمارا در چیه؟ بدون ماشین تورینگ بگید. مرسی

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

---

حالا احتمال کج فهمی منم وجود داره
اگه ممکنه دوستان جواب سوال ضمیمه رو بدند و بگن کدوم گزینه صحیحه؟
اینطوری فکر کنم بهتر بتونیم در مورد گزینه صحیح تصمیم بگیریم

ببینید دوست عزیز همه حرف های شما درسته و هیج جایی از قضایا علط نیست و همه‌ی حرف های من هم درسته چون هر دومون داریم قضایایی که درستن رو میگیم

ببینید ایا این روش حل درسته که برای ثابت کردن P ---->q ما درست بودن q ---> p ثابت کنیم ؟ خب نه شما هم روی سوال رو درست میگیرید و ثابت می کنید۱ درسته

اما باید توجه کنین که روی سوال گفته L مفروضه وبرای کدام یک از گزینه‌ها میشه ماشین تورینگ کشید که برای همه‌ی رشته هاش متوقف بشه یعنی باید با درست دونستن گزینه ای ثابت کنیم L بازگشتی شمارشیه
اگه اینجوری سوال رو بخونید ودر نظر بگیرید می بینید که گزینه ۱ غلطه چون نمیشه نتیجه گرفت که L یه re
یعنی نمی تونیم بگیم
[tex]L\in RE ,\bar{L}\notin RE \rightarrow L\in RE[/tex]

اگه میگید میشه واقعا ثابت کنید
و همینطور در گزینه ۲ نمیشه نتیجه گرفت

[tex]L\in RE ,\bar{L}\notin R \rightarrow L\in RE[/tex]

اگه میگید میشه واقعا ثابت کنید

اما در گزینه ۳ ما می تونیم با داشتن اون شرایط بگیم که L حتما R اه و چون همه‌ی R زیر مجموعه‌ی re اند پس L هم RE

یعنی بگیم

[tex]L\in RE ,\bar{L}\in RE \rightarrow L\in R \rightarrow L\in RE[/tex]

و این مطلب اصلا یه قضیه است و شما هم مطمئنم می دونید


طراح از اون طراح‌ها بوده و سوال رو جوری پیچونده بوده که نشه به آسونی به جواب رسید
وگرنه بنده خدا هم گزینه درست رو انتخاب کرده و هم سوال جالبی رو طرح کرده .

۱ - چون گفته برای تمام رشته‌ها ماشین تورینگ باید HALT داشته باشه پس باید بازگشتی باشه . گزینه سه درسته.
۲ - خیلی خودمونی می گم‌:
زبان بازگشتی‌: یه الگوریتم عضویته یعنی اگر w رو بهش بدی جواب قطعی بهت می ده که عضو زبان هست یا نه .
زبان بازگشتی شمارا‌: یه الگوریتم تشخیص دهنده هست .یعنی اگر w رو بهش بدی فقط می تونه بگه عضو زبان هست راجب به عضو زبان نبودنش قطعی نمی تونه جواب بده چون دو حالت براش اتفاق می افته .
۳ - ۱۰۰% نمی شه. چون زبان های بازگشتی زیر مجموعه زبان های بازگشتی شمارا هستند(طبق نمودار چامسکی)
۴ - ۱۰۰% نمی شه.چون زبان های منظم زیر مجموعه مستقل از متن هستند (طبق نمودار چامسکی)

بچه‌ها اگه ممکنه جواب ایندوتا سوال رو هم بدید
البته با دلیل
متشکرم


[من این پست رو سومین دفعه نوشتم و احساس می کنم پاک میشه‌، فکر نکنم با قوانین سایت مغیر باشه!!!]

فکر میکنم هر دو سوال گزینه ۱ درست باشه.
در هر دو سوال گفته ماشین بر روی جملات عضو زبان توقف میکنه ،پس تا اینجا قطعا بازگشتی شمارا ست. اگه با رشته های غیر عضو هم توقف داشت بازگشتی هم میشد ،ولی در مورد رشته های غیر عضو حرفی نزده! ممکنه با اونها متوقف بشه یا تو لوپ بیفته.
پس چیزی که تا اینجا در موردش قطعیت داریم همون بازگشتی شمارا ست که تحت مکمل بسته نیست.

جواب من:
سوال ۵۸ گزینه ۱
سوال ۶۰ گزینه ۳

درسته؟!

(۰۱ دى ۱۳۹۰ ۱۱:۲۹ ق.ظ)باد نوشته شده توسط:  جواب من:
سوال ۵۸ گزینه ۱
سوال ۶۰ گزینه ۳

درسته؟!

ببینید اینطوری که من تحقیق کردم کسی کاملا بر این موضوعات مسلط نیست و کنکور سال ۸۹ به طرز عجیبی این موضوع رو نشون داده و از کسی هم که در این زمینه‌ها مطالعه کردن می پرسیم هر کسی با یه استدلاجی یه جوابی میده و تعداد اندکی استدلالات منو نمی پذیرند و بقیه می پذیرند.
حالا یا من اشتباه می کنم یا دیگران
اینجا فعلا کار به گزینه صحیح نداریم.
من میخوام ببینم هر کسی چه استدلالی داره.
اگه ممکنه شما هم استدلالتون رو بگید
مشتکرم

نقل قول: خوب حالا بگید جوابشو!
اینجوری با اطمینان بیشتر آدم جواب می ده! نظریه همینجوریشم ترسناکه!

گفتم که
جواب صحیحی فعلا یافته نشده. هر کسی یه جوابی می ده و منم یه جوابی
تنها ترسم اینه که نظریات من با آزمون پارسه درسته ولی با جواب سنجش کاملا متفاوت.
احساس می کنم اندک افرادی هستند که این موضوع رو درک کردند و بخاطر همین هم خیلی ازش تو ارشد سوال نمیاد و تا حالا هم که اومده به نظرم تستهاش استاندارد نبوده و طراح سوال یه جورایی گیج زده خودش
مثلا همین سوال سال ۸۹ (سوال ۶۰) رو نگاه کنید.
من استدلالم اینه گزینه یک صحیحه و کاملا هم با دلیل می گم ولی سنجش گفته سه و همین باعث شده به اطلاعاتم شک کنم
اگه سنجش یه بازنگری کنه چه خوب می شه. حداقل تکلیف من با خودم مشخص میشه

جواب سازمان سنجش چی بوده؟ من که الان اصلا یادم نیست ولی از اونجایی که این سوالای کنکور من بود یادمه که جواب سوالای نظریه سنجش همش درست بود سال ۸۹/

---

البته سوال ۵۸ تو اصلاحیه درست شده. شده گزینه ۴!

(۰۲ دى ۱۳۹۰ ۱۲:۲۶ ق.ظ)luna نوشته شده توسط:  جواب سازمان سنجش چی بوده؟ من که الان اصلا یادم نیست ولی از اونجایی که این سوالای کنکور من بود یادمه که جواب سوالای نظریه سنجش همش درست بود سال ۸۹/

---

البته سوال ۵۸ تو اصلاحیه درست شده. شده گزینه ۴!

سوال ۶۰ جواب گزینه سه بوده
ابتدای این تاپیک صورت سوال رو قرار دادم
شما هم اگه بتونید راهنمایی کنید ممنون می شم

کسی نیست مرا یاری کند/.؟