کسی ۵۳ رو نزده ؟
بالاخره ۵۴ گزینه ۲ میشه یا ۴؟
سلام
سوال ۵۳- الف ج د (شاید هم ب ج د)
د: هر زبان دلخواه از الفبا که توسط یک گرامر صوری تولید شدنی باشد بازگشتی است. غلط ؛ گرامرهای نامقید (نوع۰) زبان های بازگشتی شمارش پذیر تولید میکنند و ممکن است بازگشتی نباشند.
د واضح ترین گزینه است که غلطه پس بین گزینه الف ج د و ب ج د یکیش میشه و ج قطعا غلطه.
الف: هر زبان دلخواه بر الفبا شمارش پذیر است. غلط ؛ اگه اینطوری بود مجموع همه زبانها شمارش پذیر بود و زبانی که بازگشتی شمارش پذیر نباشه نداشتیم که اینگونه نیست و زبانهایی وجود دارند که بازگشتی شمارش پذیر نیستند.
ب: مجموعه تمامی زبانهای ممکن از الفبا شمارش پذیر است. فکر میکنم نکتش تو کلمه ممکنشه , وقتی گفته ممکن منظورش اینه که میشه با ماشین تولیدش کرد.
البته این تنها استدلالی بود که من میتونستم بکنم ؛ تا طراح منظورش چی بوده و چطور فکر کرده!!!
سوال ۵۴- گزینه صحیح وجود ندارد
برای هر گزینه یه مثال نقض میارم
۱- & , a , b z=ab, y=b , x=a ؛ yz=bab عضو زبان نیست اما xz=aab عضو زبان هست.
۲- ab , aab , b z=ab , y=b , x=a ؛ yz=bab عضو زبان نیست اما xz=abab عضو زبان هست.
۳- & , a , aa , b مثل گزینه یک
۴- & , a , ab , aab z=aab , y=aab , x=a ؛ yz=aabaab عضو زبان هست اما xz=aaab عضو زبان نیست.
البته گزینه ۴ فقط در همین صورت اشتباه در میاد شاید طراح هواسش نبوده و کلید رو ۴ اعلام کنن.
من اول گفتم بزنم ۴ رو زدم که اگه اینطوری اشتباه کرده باشه تستو از دست ندم اما باز پاکش کردم گفتم به اینا اعتباری نی!
البته این تست رو هم تا طراح چی فکر کرده باشه!!!
سوال ۵۵- SaS/aSbS/&
واسه گزینه های دیگه مثال نقض میارم:
SaS/aSb/& aba رو نمیتونه تولید کنه.
S Sb/aSSb/a aa رو نمیتونه تولید کنه علاوه بر اون با Sb میشه هرچقدر که بخوای b تولید کنی۱
S aS/Sa/aSb/ab aa رو تولید نمیکنه.
سوال ۵۶- نمدونم!
هرچی فکر کردم چیزی از مغزم تراوش نکرد! فکر کنم فقط اونایی که نکتشو خوندن بتونن بزنن, استدلالش "به نظر میاد سخته" اما تست قشنگیه. اگه کسی استدلالی داره یا از یه استاد معتبر نکتشو شنیده بگه.
سوال۵۷- الف ب د
واضحه که L2 حساس به متنه و L1 مستقل از متن غیرقطعی. اگه کسی شک داره تو کتاب پترلینز هردوش هست, البته اثباتشم کاری نداره.
الف- L1 مستقل از متن است اما مستقل از متن قطعی نیست. درست
ب- اگر L1 مستقل ازمتن قطعی باشد آنگاه L1UL2 مستقل از متن است. جمله شرطیه و در جمله شرطی اگه مقدمش False باشه تالی هرچی که باشه جمله درسته. در واقع از False هر نتیجه ای که بگیریم درسته.
ج-L1UL2 مستقل از متن است. غلطه حساس به متن میشه.
د-اگرL2 مستقل از متن باشد L1 مستقل از متن است. بازم مقدم False هست و جمله درسته, در شرایطی که اگر مقدم True هم میبود چون تالی هم True هست بازم میشد درست.
سوال ۵۳
اون سوالی که چه جملاتی غلطه به غیر از الف همه غلطه
الف درسته چون رشته های تک عضوی دو عضوی و .... از یک زبان قابل شمارش هستند و میشه با N تناظر پیدا کنند البته نامتناهی برای بعضی زبانها (یعنی شمارش پذیر و بسته به نوع زبان متناهی یا نامتناهی)
ب غلطه و واضح
ج هم که در تمام گزینها هست !!
گزینه دال هم بازگشتی غلطه و اگه بازگشتی شمارشی بود درست بود
سوال ۵۴
سوال هم ارزی گزینه چهار طبق دفترچه اول
هر چند که به نظرم a رو نباید توی کلاس در نظر میگرفت مفهوم سوال این بود که شما هر رشته ای از بستار زبان انتخاب کنید با اضافه کردن X یا Y به ابتدای اون باز هم این رشته جزو زبان باشه که برای ab aab و تهی این اتفاق میافته ولی طراح a رو هم اضافه داده بود در گزینه که فکر کنم بخاطر بستارهایی هست که با ab شروع میشه و با اضافه کردن یک a هم جزو زبان هست هرچند که به نظر من اشتباست چون سوال گفته هر رشته عضو بستار و رشته aabaab برای مثال یه رشته عضو بستار هست که با اضافه کردن a عضو بستار نیست
در ضمن به نظرم باید اون دوتا L های متن سوال L* باشند
کلا سوال رو نابود کردم سوال ۵۵
سوالی که باید گرامر زبان رو مینوشتیم نوشته تمام رشته هارو تولید کنه
تمام گزینها بعد از تولید b توان تولید a ندارند جز گزینه اول aSbS
سوال ۵۶
سوالی که گفته زبان گرامر چیه
به نظر من چون منظم نسبت به هر عملی بسته هست میشه یه جورایی این زبان رو ترکیب الحاق و همورفیک و بستار منظم نوشت و منظمش کرد گذاشتم برای آخر که روش کار کنم که به لطف قصه پردازی طراح سیستم عامل نرسیدم برگردم
در مورد سوال ۵۳ اگه یه قضیه کتاب لینز رو در نظر بگیریم گزاره ب درست میشه. قضیه ۳-۱۰ کتاب لینز گفته تمامی ماشینهای تورینگ گرچه نامتناهی ولی شماراست. اگر هر ماشین تورینگ رو معادل یک زبان فرض کنیم همون گزاره ب بدست میاد.
۵۳ - گزینه ۲یا۳ زدم(یادم نیست دقیق) عبارت الف غلطه چون ممکنه در تناظر یک به یک با اعداد حقیقی نباشه(یعنی دارای نظم خاصی نباشه و همچنین ممکنه نامتناهی باشه)چون گفته سیگما میتونه هر زبان دلخواهی باشه
۵۴- ۴
۵۵ - ۱
۵۶ - ۱
۵۷ -
(۲۹ بهمن ۱۳۹۰ ۰۶:۱۶ ب.ظ)fatima1537 نوشته شده توسط: گزینه ۲یا۳ زدم(یادم نیست دقیق) عبارت الف غلطه چون ممکنه در تناظر یک به یک با اعداد حقیقی نباشه(یعنی دارای نظم خاصی نباشه و همچنین ممکنه نامتناهی باشه)چون گفته سیگما میتونه هر زبان دلخواهی باشهبه نظر من که دارید اشتباه میکنید
مفهوم متناهی و شمارش پذیری رو با هم اشتباه گرفتید مثلا شما یه زبان خاص که معرفی کنید میشه گفت فلان تا رشته یک عنصری داری فلان رشته دو عنصری و .... درسته ممکنه این تناظر تموم نشه (نامتناهی) همون طور که اعداد طبیعی پایان ندارند ولی تناظر بین اون و اعداد طبیعی وجود داره (شمارش پذیر)
(۲۹ بهمن ۱۳۹۰ ۰۶:۰۴ ب.ظ)CE91 نوشته شده توسط: در مورد سوال ۵۳ اگه یه قضیه کتاب لینز رو در نظر بگیریم گزاره ب درست میشه. قضیه ۳-۱۰ کتاب لینز گفته تمامی ماشینهای تورینگ گرچه نامتناهی ولی شماراست. اگر هر ماشین تورینگ رو معادل یک زبان فرض کنیم همون گزاره ب بدست میاد.مشکل از همینه ""اگر هر ماشین تورینگ ..""، زبانهایی هست که ماقادر به نوشتن گرامر براش نیستیم
اگه نه فکر میکنید این همه تلاش که توی کتابهای نظریه برای تعریف یه ماشین قدرتمند تر از تورینگ کردند چیست مگه ماشین به همین سادگی چه عیبی داشت؟؟ مشکل اینه که تورینگ گرامرهای بدون محدودیت رو پوشش میده و نه هر زبانی رو
سوال ۵۴ به نظرم غلطه
۴ مثال نقض داره: x=a , y=lambda , z=abb
در نتیجه xz=aabb , yz=abb که xz وجود ندارد ولی yz وجود دارد
برای گزینه ۲ هم مثال نقض وجود داره
۵۷-۲
من فکر می کنم که ۵۶ هم ۱ بشه ولی مطمئن نیستم
(۲۹ بهمن ۱۳۹۰ ۰۸:۲۷ ب.ظ)reza_memari_sharif نوشته شده توسط: سوال ۵۴ به نظرم غلطهاگه نظر من رو بخوای سوال چهار کلا غلطه
۴ مثال نقض داره: x=a , y=lambda , z=abb
در نتیجه xz=aabb , yz=abb که xz وجود ندارد ولی yz وجود دارد
برای گزینه ۲ هم مثال نقض وجود داره
ولی نزدیکترین گزینه به نظرم چهار هست
دلیلش رو قبلا گفتم
در مورد سوال ۵۳/
تو کتاب پارسه صفحه ۱۶۰ نکته ۱۴ میگه:تمام رشته های تعریف شده روی الفبا زیگما استار شمارا است.بنظرتون این به معنی قسمت ب این سواله؟اگه باشه پس این گزینه درسته و الف غلطه.واسه الفم چیزای هست که نقضش کنه!
در مورد ۵۶، یک دوستی اینجوری استدلال کرد که:
هر سه گزینه‌ی ۲ و ۳ و ۴ می‌گن منظم نمیتونه باشه اصلا. در صورتی که اگر *L=a باشه، 'L هم همون میشه که منظمه. در نتیجه فقط گزینه‌ی یک امکان داره درست باشه.
به همین سادگی اشتباه می‌زنیم.
۵۶ ۹۹% گزینه یک درسته.فکر کنم تو کتاب مقسمی یا پارسه بوده این.
در مورد سؤال هم‌ارزیه:
اگر x=a و y=lambda باشه، فرض کنید z=aab باشه. داریم: yz=aab که عضو L هست. ولی xz=aaab که عضو L نیست. پس a و لامبدا با هم هم‌ارز نیستن و حتما باید جدا باشن.
اگر داشته باشیم: x=ab و y=aab. به ازای هر z که از زبان در نظر بگیریم، هم xz عضو زبان هست هم yz. پس حتما باید ab و aab عضو یک کلاس باشن. در نتیجه گزینه‌ی دوم و چهارم رد میشه.
می‌مونه گزینه‌های ۱ و ۳.
aa عضو کلاس b میشه. چون هیچ zی در L وجود نداره که اگه aa بزنیم سرش عضو زبان بشه. هر رشته‌ی زبان یا با ab شروع میشه یا با aab. در هر دو حالت رشته‌ی حاصل عضو L نمی‌شه چون با بیشتر از دوتا a شروع میشه. همین قضیه در مورد b هم صادقه که هیچ رشته‌ای در L نمیتونه با b شروع بشه.
در نتیجه گزینه‌ی ۳ هم رد میشه و پاسخ نهایی میشه گزینه‌ی ۱.
(۳۰ بهمن ۱۳۹۰ ۰۱:۱۶ ب.ظ)martianboy نوشته شده توسط: در مورد سؤال هم‌ارزیه:
اگر x=a و y=lambda باشه، فرض کنید z=aab باشه. داریم: yz=aab که عضو L هست. ولی xz=aaab که عضو L نیست. پس a و لامبدا با هم هم‌ارز نیستن و حتما باید جدا باشن.
اگر داشته باشیم: x=ab و y=aab. به ازای هر z که از زبان در نظر بگیریم، هم xz عضو زبان هست هم yz. پس حتما باید ab و aab عضو یک کلاس باشن. در نتیجه گزینه‌ی دوم و چهارم رد میشه.
می‌مونه گزینه‌های ۱ و ۳.
aa عضو کلاس b میشه. چون هیچ zی در L وجود نداره که اگه aa بزنیم سرش عضو زبان بشه. هر رشته‌ی زبان یا با ab شروع میشه یا با aab. در هر دو حالت رشته‌ی حاصل عضو L نمی‌شه چون با بیشتر از دوتا a شروع میشه. همین قضیه در مورد b هم صادقه که هیچ رشته‌ای در L نمیتونه با b شروع بشه.
در نتیجه گزینه‌ی ۳ هم رد میشه و پاسخ نهایی میشه گزینه‌ی ۱.
اگه x=a و y=lambda که گزینه یک هم رد میشه چون میشه رشته ای مثه aab داشت که yz عضو زبان هست ولی xz نیست و چون متن سوال گفته به ازای هر z دلخواه گزینه شما هم رد میشه
در ضمن اگه با این فرض شما بخوایم ادامه بدیم کلاس هم ارزی خیلی وسیع تر از این حرفاست میشه همه رشته های aaa bb , ba, bab و خلاصه بی نهایت رشته رو هم ارز گرفت
به نظر من گزینه چهار هست منتها a رو طراح اشتباه آورده و یا اینکه متن سوال باید این شکلی تغییر کنه "وجود دارد zعضو L*" و چون اگه این جمله رو اضافه کنه اون طور به رای شما گزینه یک هم درست میشه به نظرم همون a رو اشتباه آورده و فکر کرده چون رشته هایی که با ab آغاز میشند برش صادقه پس جزو هم ارزی هست
(۳۰ بهمن ۱۳۹۰ ۰۱:۳۷ ب.ظ)موج نوشته شده توسط: اگه x=a و y=lambda که گزینه یک هم رد میشه چون میشه رشته ای مثه aab داشت که yz عضو زبان هست ولی xz نیست و چون متن سوال گفته به ازای هر z دلخواه گزینه شما هم رد میشه
در ضمن اگه با این فرض شما بخوایم ادامه بدیم کلاس هم ارزی خیلی وسیع تر از این حرفاست میشه همه رشته های aaa bb , ba, bab و خلاصه بی نهایت رشته رو هم ارز گرفت
به نظر من گزینه چهار هست منتها a رو طراح اشتباه آورده و یا اینکه متن سوال باید این شکلی تغییر کنه "وجود دارد zعضو L*" و چون اگه این جمله رو اضافه کنه اون طور به رای شما گزینه یک هم درست میشه به نظرم همون a رو اشتباه آورده و فکر کرده چون رشته هایی که با ab آغاز میشند برش صادقه پس جزو هم ارزی هست
دوست عزیز این چیزی که شما گفتی می‌خواستی حرف من رو رد کنی؟ این که حرف من رو گفت درسته.
این حرف شما نشون میده که لامبدا و a نمی‌تونن توی یک کلاس باشن. پس حتما باید جدا آورده بشن. منم همینو گفتم. گزینه ۱ رد نمی‌شه که.گزینه‌ی ۴ هم غلطه چون رشته‌های لامبدا و ab و aab هم‌ارزن. با یه کم دقت متوجهش می‌شی.
رشته‌های دیگه‌ای هم که شما آوردی همه‌شون هم‌ارز می‌شن با b.
دقت کنید که این سه عضو، کوچک‌ترین نماینده‌های کلاسشون هستن و به خاطر سادگی اینجوری نمایش داده شدن. هر کلاس ممکنه بی‌نهایت عضو داشته باشه:
- کلاس a تک عنصریه. چون فقط همین رشته‌س که اگه سر چندتا از اعضای زبان بزنیمش بازم حاصل عضو زبان باشه. مثالش هم رشته‌ی ab هستش. تمام رشته‌های ممکن دیگه، یا توی زبان هستن که می‌شن هم‌ارز با لامبدا. یا توی زبان نیستن که می‌شن هم‌ارز با b.
- کلاس b تمام رشته‌هایی که عضو زبان L نیستن عضو کلاسش هستن. تنها استثنا رشته‌ی a هستش که کلاس جدایی داره.
- کلاس لامبدا شامل همه‌ی رشته‌های توی زبانه.
متاسفانه خودم هم این سؤال رو به اشتباه زدم گزینه‌ی ۳ که الان دیدم غلطه.