سال ۹۱ مهندسی کامپیوتر بحث و بررسی سوالات
پاسخ های سنجش:
۵۳- ۴
۵۴- ۳
۵۵- ۱
۵۶- ۱
۵۷- ۲
(۲۸ بهمن ۱۳۹۰ ۰۶:۲۴ ب.ظ)mp1368 نوشته شده توسط: اون سوال که گفته بود هر پیشوند دلخواه رو که بگیریم تعداد aها حداقل باید به اندازه تعداد bها باشه چی زدین؟فکر می کنم همین رو زدم.
هر چهار تا این پیشوند رو تولید می کردن ولی توی سر سوال گفته بود هر رشتهی دلخواه رو باید تولید کنه که تو دفترچه C یک و چهار رشته a رو تولید نمی کردن و توی گزینه دو و سه من
as|asbs|LAMBDA رو زدم
(۲۸ بهمن ۱۳۹۰ ۰۶:۲۴ ب.ظ)mp1368 نوشته شده توسط: اون سوال که گفته بود هر پیشوند دلخواه رو که بگیریم تعداد aها حداقل باید به اندازه تعداد bها باشه چی زدین؟منم همینو زدم
هر چهار تا این پیشوند رو تولید می کردن ولی توی سر سوال گفته بود هر رشتهی دلخواه رو باید تولید کنه که تو دفترچه C یک و چهار رشته a رو تولید نمی کردن و توی گزینه دو و سه من
as|asbs|LAMBDA رو زدم
(۲۸ بهمن ۱۳۹۰ ۰۶:۲۴ ب.ظ)mp1368 نوشته شده توسط: اون سوال که گفته بود هر پیشوند دلخواه رو که بگیریم تعداد aها حداقل باید به اندازه تعداد bها باشه چی زدین؟
هر چهار تا این پیشوند رو تولید می کردن ولی توی سر سوال گفته بود هر رشتهی دلخواه رو باید تولید کنه که تو دفترچه C یک و چهار رشته a رو تولید نمی کردن و توی گزینه دو و سه من
as|asbs|LAMBDA رو زدم
(۲۸ بهمن ۱۳۹۰ ۰۶:۲۴ ب.ظ)mp1368 نوشته شده توسط: اون سوال که گفته بود هر پیشوند دلخواه رو که بگیریم تعداد aها حداقل باید به اندازه تعداد bها باشه چی زدین؟
هر چهار تا این پیشوند رو تولید می کردن ولی توی سر سوال گفته بود هر رشتهی دلخواه رو باید تولید کنه که تو دفترچه C یک و چهار رشته a رو تولید نمی کردن و توی گزینه دو و سه من
as|asbs|LAMBDA رو زدم
(۲۸ بهمن ۱۳۹۰ ۰۷:۱۹ ب.ظ)hamidkhl نوشته شده توسط:منم همینو(28 بهمن ۱۳۹۰ ۰۶:۲۴ ب.ظ)mp1368 نوشته شده توسط: اون سوال که گفته بود هر پیشوند دلخواه رو که بگیریم تعداد aها حداقل باید به اندازه تعداد bها باشه چی زدین؟منم همینو زدم
هر چهار تا این پیشوند رو تولید می کردن ولی توی سر سوال گفته بود هر رشتهی دلخواه رو باید تولید کنه که تو دفترچه C یک و چهار رشته a رو تولید نمی کردن و توی گزینه دو و سه من
as|asbs|LAMBDA رو زدم
(۲۸ بهمن ۱۳۹۰ ۰۹:۳۵ ب.ظ)fatima1537 نوشته شده توسط:-==--=-==--=-==--==-=--=-=-==--=-=(28 بهمن ۱۳۹۰ ۰۶:۲۴ ب.ظ)mp1368 نوشته شده توسط: as|asbs|LAMBDAمن هم همین گزینه رو زدم
(۲۸ بهمن ۱۳۹۰ ۱۰:۵۷ ب.ظ)fmka2f نوشته شده توسط: یک سوال دیگر
مجموعه A را شمارش پذیر می نامیم اگر A متناهی یا در تناظر یک به یک با مجموعه اعداد طبیعی باشد.در غیر این صورت A را ناشمارا می گوییم.فرض کنید ∑ یک الفبای متناهی دلخواه باشد.کدام گزینه از گزینه های زیر صحیح نیستند؟
الف-هر زبان دلخواه بر الفبای ∑ شمارش پذیر است
ب- مجموعه تمامی زبانهای ممکن از الفبای ∑ شمارش پذیر است.
ج- برای هر زبان دلخواه از الفبای ∑ میتوان یک گرامر صوری تولید کننده در نظر گرفت
د- هر زبان دلخواه از الفبای ∑ که توسط یک گرامر صوری تولید شدنی باشد بازگشتی است.
۱- ب و ج ۲- الف و ب و ج ۳- الف و ج و د ۴- ب و ج و د
(۲۸ بهمن ۱۳۹۰ ۱۱:۰۴ ب.ظ)irisadaf نوشته شده توسط:(28 بهمن ۱۳۹۰ ۰۹:۰۸ ب.ظ)afshinmu نوشته شده توسط:(28 بهمن ۱۳۹۰ ۰۶:۲۴ ب.ظ)mp1368 نوشته شده توسط: اون سوال که گفته بود هر پیشوند دلخواه رو که بگیریم تعداد aها حداقل باید به اندازه تعداد bها باشه چی زدین؟
هر چهار تا این پیشوند رو تولید می کردن ولی توی سر سوال گفته بود هر رشتهی دلخواه رو باید تولید کنه که تو دفترچه C یک و چهار رشته a رو تولید نمی کردن و توی گزینه دو و سه من
as|asbs|LAMBDA رو زدم
مطمئنا رشته پوچ باید پذیرفته بشه . پس در دفترچه C فقط دو گزینه ۲و۳ میتونن درست باشن که از بین اونها هم کاملا جواب مشخص بود چون گزینه ۲ bها همش میتونست اضافه بشه( اگه دقیق یادم مونده باشه ). درسته؟پس ۳ میشه نه؟
منم همینا زدم ولی همش غلط بود اگه بخواهیم رشته ای که اولش b بیاد را با هیچ کدوم نمیشه نشون داد
(۲۹ بهمن ۱۳۹۰ ۰۶:۱۶ ب.ظ)fatima1537 نوشته شده توسط: گزینه ۲یا۳ زدم(یادم نیست دقیق) عبارت الف غلطه چون ممکنه در تناظر یک به یک با اعداد حقیقی نباشه(یعنی دارای نظم خاصی نباشه و همچنین ممکنه نامتناهی باشه)چون گفته سیگما میتونه هر زبان دلخواهی باشهبه نظر من که دارید اشتباه میکنید
(۲۹ بهمن ۱۳۹۰ ۰۶:۰۴ ب.ظ)CE91 نوشته شده توسط: در مورد سوال ۵۳ اگه یه قضیه کتاب لینز رو در نظر بگیریم گزاره ب درست میشه. قضیه ۳-۱۰ کتاب لینز گفته تمامی ماشینهای تورینگ گرچه نامتناهی ولی شماراست. اگر هر ماشین تورینگ رو معادل یک زبان فرض کنیم همون گزاره ب بدست میاد.مشکل از همینه ""اگر هر ماشین تورینگ ..""، زبانهایی هست که ماقادر به نوشتن گرامر براش نیستیم
(۲۹ بهمن ۱۳۹۰ ۰۸:۲۷ ب.ظ)reza_memari_sharif نوشته شده توسط: سوال ۵۴ به نظرم غلطهاگه نظر من رو بخوای سوال چهار کلا غلطه
۴ مثال نقض داره: x=a , y=lambda , z=abb
در نتیجه xz=aabb , yz=abb که xz وجود ندارد ولی yz وجود دارد
برای گزینه ۲ هم مثال نقض وجود داره
(۳۰ بهمن ۱۳۹۰ ۰۱:۱۶ ب.ظ)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 آغاز میشند برش صادقه پس جزو هم ارزی هست
(۳۰ بهمن ۱۳۹۰ ۰۲:۲۴ ب.ظ)martianboy نوشته شده توسط: دوست عزیز این چیزی که شما گفتی میخواستی حرف من رو رد کنی؟ این که حرف من رو گفت درسته.این حرف شما نشون میده که لامبدا و a نمیتونن توی یک کلاس باشن. پس حتما باید جدا آورده بشن. منم همینو گفتم. گزینه ۱ رد نمیشه که.
گزینهی ۴ هم غلطه چون رشتههای لامبدا و ab و aab همارزن. با یه کم دقت متوجهش میشی.
رشتههای دیگهای هم که شما آوردی همهشون همارز میشن با b.
دقت کنید که این سه عضو، کوچکترین نمایندههای کلاسشون هستن و به خاطر سادگی اینجوری نمایش داده شدن. هر کلاس ممکنه بینهایت عضو داشته باشه:متاسفانه خودم هم این سؤال رو به اشتباه زدم گزینهی ۳ که الان دیدم غلطه.
- کلاس a تک عنصریه. چون فقط همین رشتهس که اگه سر چندتا از اعضای زبان بزنیمش بازم حاصل عضو زبان باشه. مثالش هم رشتهی ab هستش. تمام رشتههای ممکن دیگه، یا توی زبان هستن که میشن همارز با لامبدا. یا توی زبان نیستن که میشن همارز با b.
- کلاس b تمام رشتههایی که عضو زبان L نیستن عضو کلاسش هستن. تنها استثنا رشتهی a هستش که کلاس جدایی داره.
- کلاس لامبدا شامل همهی رشتههای توی زبانه.
(۰۳ اسفند ۱۳۹۰ ۱۲:۴۸ ق.ظ)cormen نوشته شده توسط: نکته ای راجع به سوال ۵۵:
تمام رشته های گزینه ۲ به b ختم میشوند در صورتیکه رشته ای مانند aaa جز زبان است گزینه ۳ هم رشته تهی را تولید نمیکند گزینه ۴ هم رشته abab را که جز زبان است را نمیتواند تولید کند واضح است که گزینه ۱ جواب نهایی است
(۲۸ بهمن ۱۳۹۰ ۱۱:۳۱ ب.ظ)shervinrs نوشته شده توسط: ۵۴ رو حتما من غلط زدم.
اما میشه یکی توضیح بده که چجوری [a] خالی قبوله؟
نظریه ۵ تا بود؟
جمعا ۲۷ تا سوال بود پس؟
(۰۵ اسفند ۱۳۹۰ ۰۸:۲۲ ب.ظ)mohammad_13690 نوشته شده توسط:(28 بهمن ۱۳۹۰ ۱۱:۳۱ ب.ظ)shervinrs نوشته شده توسط: ۵۴ رو حتما من غلط زدم.
اما میشه یکی توضیح بده که چجوری [a] خالی قبوله؟
نظریه ۵ تا بود؟
جمعا ۲۷ تا سوال بود پس؟
سوال ۵۴ شاید باورتون نشه(!) اما گزینه ۳ درسته؛ هرچند خود من اشتباها بین ۲ و ۴ شک داشتم و زدم ۴
واقعا گزینه ۳ درسته با این استدلال:
مفهوم کلاس هم ارزی: میخواهیم رشته ها را به چند بخش افراز کنیم تا هر رشته با توجه به رابطه موجود فقط در یکی از کلاس ها قرار گیرد (و نه بیش از یک کلاس و نه هیچ کلاس)
از هریک از این کلاس ها یک [سرگروه] می نویسیم
چهار سرگروه این مثال عبارت اند از [a] [b] [aa] [e]
هر رشته ای به نام x که مثال بزنید، با توجه به رابطه با یکی از این y ها هم ارز است (صورت سوال را دوباره بخوانید)
۱) فقط با اضافه کردن *(ab+aab) آخر آن رشته، داخل L خواهد بود => مثل [e]
۲) با اضافه کردن هیچ چیز آخر آن رشته، داخل L نخواهد بود => مثل [b]
۳) با aa پایان یافته و فقط با اضافه کردن *( b. (ab+aab داخل L خواهد بود => مثل [aa]
۴) با a پاین یافته و فقط با اضافه کردن * (b+ab). (ab+aab ) داخل L خواهد بود => مثل [aa]
برای شفاف سازی بیشتر چهار کلاس همراه سرگروه و مثال:
[e] =
{ab,aab,abaab,...}
[a] =
{aba,aaba,abaaba,...}
[aa] =
{abaa,aabaa,abaabaa,...}
[b] =
{ba,bbaa,babaaaabb,abb,...}
(۰۶ اسفند ۱۳۹۰ ۰۴:۲۴ ب.ظ)cormen نوشته شده توسط: دوست عزیز چه رشته ای به b اضافه کنیم تا عضو زبان L بشه؟
بهتره شما صورت سوال رو به دقت بخونی چون گفته xz عضو L اگر و فقط اگر YZ عضو L پس کلاسی بنام b معنی نداره در ساختمان گسسته گریمالدی میگه اعضای کلاس b آنهایی هستند که با اضافه کردن هیچ یا هر رشته ای به انتهای b عضو L شوند
(۰۷ اسفند ۱۳۹۰ ۰۲:۵۶ ب.ظ)mohammad_13690 نوشته شده توسط: بله درسته، با اضافه کردن هیچ چیز به b نمیشه اون رو عضو L کرد و به همین دلیل سرگروه یکی از کلاس های هم ارزیه که همکلاسی هاش رشته هایی هستن که مثل خود b ، نمیتونن عضو L بشن؛ مثل ba,baba,bba,...
صورت سوال رو با هم میخونیم
فرض کنید x=b و y=baba و z هم که گفته هر رشته دلخواه؛ قبول دارید در این صورت x و y هم ارزند؟ چون برای هر z که xz عضو L باشه، yz هم عضو L هست (البته اگر z پیدا میشد اما الآن فرض همیشه اشتباه و استنتاج همیشه صحیح است)
(۰۸ اسفند ۱۳۹۰ ۰۵:۵۷ ب.ظ)ehsan.m نوشته شده توسط: در مورد سوال ۵۳ گزینه ۳ هم می توانید درست باشد چون مورد اول حتما غلط است و یک قضیه در کتاب پیتر به شمار ۲-۱۱ گفته که زبانهای وجود دارند که بازگشتی برشمردنی نیستد روی الفبای غیر تهی سیکما در نتیجه هر زبان روی سیکما شمارش پذیر نیست و گزینه ۳ هم می تواند درست باشدموافقم
(۰۹ اسفند ۱۳۹۰ ۰۵:۰۴ ب.ظ)anyone نوشته شده توسط: در مورد سوال ۵۳
به نظر شما زبانی وجود دارد که بشه براش گرامری نوشت اما الگوریتمی براش وجود نداشته باشه؟
وجود گرامر برای تشخیص اینکه زبان تصمیم پذیر هست کافی نیست؟
(۱۳ اسفند ۱۳۹۰ ۰۹:۰۴ ب.ظ)tarang نوشته شده توسط: سوال ۵۳
گزینه ج )برای هر زبان دلخواه از الفبای سیکما می توان یک گرامر صوری تولید کننده در نظر گرفت
اگر الف درست باشه ج هم باید درست باشه چون هر زبانی بازگشتی برشمردنی باشه می توان برای ان یک گرامر نامقید پیدا کرد
اگر الفبای یک سیکما متناهی باشه انگاه ان مجموعه شمارش پذیره ولی هر زبان ان مجموعه شمارش پذیر نیست این تصویر کتاب لینز که پیوست کردم میگه به ازای هر سیکمای غیر تهی زبانهای وجود دارند که بازگشتی برشمردنی نیستند بعد هم نگفته مجموعه متناهی باشه یا نامتناهی
(۱۳ اسفند ۱۳۹۰ ۱۰:۰۱ ب.ظ)موج نوشته شده توسط:(13 اسفند ۱۳۹۰ ۰۹:۰۴ ب.ظ)tarang نوشته شده توسط: سوال ۵۳
گزینه ج )برای هر زبان دلخواه از الفبای سیکما می توان یک گرامر صوری تولید کننده در نظر گرفت
اگر الف درست باشه ج هم باید درست باشه چون هر زبانی بازگشتی برشمردنی باشه می توان برای ان یک گرامر نامقید پیدا کرد
اگر الفبای یک سیکما متناهی باشه انگاه ان مجموعه شمارش پذیره ولی هر زبان ان مجموعه شمارش پذیر نیست این تصویر کتاب لینز که پیوست کردم میگه به ازای هر سیکمای غیر تهی زبانهای وجود دارند که بازگشتی برشمردنی نیستند بعد هم نگفته مجموعه متناهی باشه یا نامتناهی
قسمت د که غلط بودنش مشخص هست و اصلا روش هیچ بحثی نیست باید به جای کلمه بازگشتی از بازگشتی برشمردنی استفاده میکرد ( قسمت د غلط)
در همین پیوست خودتون :
آخرین جمله داره تاکید میکنه که هر زبان سیگما قابل شمارش نیست (یعنی ج غلط)
همین طور داره میگه بر طبق تئوری ۱۱/۱ مجموعه زبان های سیگما هم غیر قابل شمارش هست (ب غلط)
پس تا همینجا میشه گزینه چهارم رو به عنوان جواب انتخاب کرد
شما در صورتی میتونی قسمت الف رو رد کنی که یا یه جمله در لینز پیدا کنی که صریحا مخالف الف باشه
ویا هم ارزی دو جمله الف و ج رو از لینز بیان کنی من کمی تردید دارم که هم ارز باشند !!
در هر صورت من هم سر کنکور بین همین تردید داشتم ولی از اونجایی که اون سه تای دیگه به صورت واضح و مشخص غلط بود و گزینه ای هم نبود که بگه هر چهار تا غلطه گزینه چهارم رو انتخاب کردم
(۱۴ اسفند ۱۳۹۰ ۰۲:۴۷ ب.ظ)anyone نوشته شده توسط: در مورد سوال ۵۶ من نمی تونم دلیل منظم بودنشو درک کنم کسی میتونه اینو اثبات کنه؟منم نمیتونم بفهمم چطوری این زبان منظم حساب میشه!
نظرم اینه که اینکه یه زبان زیر مجموعه یه زبان منظم باشه دلیلی بر منظم بودن خودش نیست (مثلا a به توان n فاکتوریل)
(۱۴ اسفند ۱۳۹۰ ۰۸:۳۹ ب.ظ)tarang نوشته شده توسط: قضیه ۱-۱۱ میگه اگر یک مجموعه نامتناهی شمارا باشد مجموعه توانی آن ناشمارا است.سوال گفته مجموعه متناهییه پس با این قضیه نمیشه گزینه ۲ را رد کرد.به نظر شما این جمله که اگر یک مجموعه متناهی باشه انگاه مجموعه توانی ان شمارش پذیره اشتباست
(۱۴ اسفند ۱۳۹۰ ۰۸:۵۴ ب.ظ)موج نوشته شده توسط:ترجمه متن گفته چون سیگما * نامتناهی است قضیه ۱۱-۱ به ما می گوید که مجموعه تمامی زبانهای روی سیگما ناشمارا است حرف شما درست ولی با استفاده از قضیه ۲-۱۱ الف ۱۰۰% غلطه ولی برای رد ۲ قضیه نداریم ولی توضیحات بعد از قضیه ۲-۱۱ میشه ۲ هم رد کرد(14 اسفند ۱۳۹۰ ۰۸:۳۹ ب.ظ)tarang نوشته شده توسط: قضیه ۱-۱۱ میگه اگر یک مجموعه نامتناهی شمارا باشد مجموعه توانی آن ناشمارا است.سوال گفته مجموعه متناهییه پس با این قضیه نمیشه گزینه ۲ را رد کرد.به نظر شما این جمله که اگر یک مجموعه متناهی باشه انگاه مجموعه توانی ان شمارش پذیره اشتباست
من عینا ترجمه متن همون پیوست لینزتون رو گفتم
theorem 11.1 tells us that the set of all languages on "E" is not countable
تئوری ۱۱/۱ این را بیان میکند که مجموعه همه زبانها بر روی الفبای سیگما قابل شمارش نیستند (دقیقا ناقض ب هست)
در ضمن نقض این قسمت هم مثل قسمت د کاملا آشکاره و کسی که یه دور هم سرسرکی نظریه خونده باشه میتونه این دو تا رو اول رد کنه
موفق باشید
(۱۴ اسفند ۱۳۹۰ ۱۱:۱۰ ب.ظ)mohammad_13690 نوشته شده توسط:(14 اسفند ۱۳۹۰ ۱۲:۳۹ ق.ظ)esi نوشته شده توسط: در مورد سوال ۵۴ ، نظرتون چیه ؟؟؟استدلال من تو پستهای قبلی مشکل داشت یا قابل فهم نبود؟
چطور میشه گزینه ۳ درست میشه؟؟
اصلا b چطوری می تونه پیشوند باشه یعنی x=b یا y=b باشه ؟؟؟
گزینه ۴ درست نیست بنظرتون ؟؟؟
(۱۴ اسفند ۱۳۹۰ ۱۱:۳۹ ب.ظ)esi نوشته شده توسط: من واقعا متوجه نشدم ، من کلا مشترک ۳ تا غلط زدم که یکیش همینه ، اما واقعا منظورتونو دقیق ندونستم ، اصلا مگه b می تونه پیشوند باشه !!؟؟؟ شاید هم من قاطی کردم !!!؟؟؟
(۱۷ اسفند ۱۳۹۰ ۰۹:۲۱ ب.ظ)annmary نوشته شده توسط: دوستان در مورد سوال ۵۴ یه نگاهی به صفحه ۴۱ و ۴۲ این پی دی اف بندازید (سوال ۱)جواب سوال۵۴ رو از پی دی اف کات و ضمیمه کردم
با کمی تغییر گویا طراح سوال منظورش همین بوده
البته هم ارزی کلاس رو جور دیگه ای تعریف کرده که ظاهرا جواب داخل همین پی دی افه
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.