(۳۰ بهمن ۱۳۹۰ ۰۲:۲۴ ب.ظ)martianboy نوشته شده توسط: دوست عزیز این چیزی که شما گفتی می‌خواستی حرف من رو رد کنی؟ این که حرف من رو گفت درسته.این حرف شما نشون می‌ده که لامبدا و a نمیتونن توی یک کلاس باشن. پس حتما باید جدا آورده بشن. منم همینو گفتم. گزینه ۱ رد نمیشه که.
گزینه‌ی ۴ هم غلطه چون رشته‌های لامبدا و ab و aab هم‌ارزن. با یه کم دقت متوجهش می‌شی.
رشته‌های دیگه‌ای هم که شما آوردی همه‌شون هم‌ارز می‌شن با b.
دقت کنید که این سه عضو، کوچک‌ترین نماینده‌های کلاسشون هستن و به خاطر سادگی اینجوری نمایش داده شدن. هر کلاس ممکنه بی‌نهایت عضو داشته باشه:متاسفانه خودم هم این سؤال رو به اشتباه زدم گزینه‌ی ۳ که الان دیدم غلطه.
- کلاس a تک عنصریه. چون فقط همین رشته‌س که اگه سر چندتا از اعضای زبان بزنیمش بازم حاصل عضو زبان باشه. مثالش هم رشته‌ی ab هستش. تمام رشته‌های ممکن دیگه، یا توی زبان هستن که می‌شن هم‌ارز با لامبدا. یا توی زبان نیستن که می‌شن هم‌ارز با b.
- کلاس b تمام رشته‌هایی که عضو زبان L نیستن عضو کلاسش هستن. تنها استثنا رشته‌ی a هستش که کلاس جدایی داره.
- کلاس لامبدا شامل همه‌ی رشته‌های توی زبانه.
میدونی چیه ؟
من دارم یه کلاس هم ارزی میگیرم همش رو
شما هر کدوم رو یه نماینده یه کلاس
که البته سوال به حرف شما شبیه تره
بیخیال دیگه اصلا تا قبل کلید نظر نمیدم
فقط اعصاب آدم بیشتر خورد میشه
موفق باشید
نکته ای راجع به سوال ۵۵:
تمام رشته های گزینه ۲ به b ختم میشوند در صورتیکه رشته ای مانند aaa جز زبان است گزینه ۳ هم رشته تهی را تولید نمیکند گزینه ۴ هم رشته abab را که جز زبان است را نمیتواند تولید کند واضح است که گزینه ۱ جواب نهایی است
(۲۸ بهمن ۱۳۹۰ ۱۱:۳۱ ب.ظ)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,...}
(۰۵ اسفند ۱۳۹۰ ۰۸:۲۲ ب.ظ)mohammad_13690 نوشته شده توسط: سوال ۵۴ شاید باورتون نشه(!) اما گزینه ۳ درسته؛ هرچند خود من اشتباها بین ۲ و ۴ شک داشتم و زدم ۴منم ۳ زدم ولی استدلالم یه جور دیگه بود تقریباً مطمئنم ۳ میشه.
واقعا گزینه ۳ درسته با این استدلال:
.....
(۰۵ اسفند ۱۳۹۰ ۰۸:۲۲ ب.ظ)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,...}
---------------------------------------
دوست عزیز چه رشته ای به b اضافه کنیم تا عضو زبان L بشه؟
بهتره شما صورت سوال رو به دقت بخونی چون گفته xz عضو L اگر و فقط اگر YZ عضو L پس کلاسی بنام b معنی نداره در ساختمان گسسته گریمالدی میگه اعضای کلاس b آنهایی هستند که با اضافه کردن هیچ یا هر رشته ای به انتهای b عضو L شوند
[tex]\lambda[/tex]
(۰۶ اسفند ۱۳۹۰ ۰۴:۲۴ ب.ظ)cormen نوشته شده توسط: دوست عزیز چه رشته ای به b اضافه کنیم تا عضو زبان L بشه؟
بهتره شما صورت سوال رو به دقت بخونی چون گفته xz عضو L اگر و فقط اگر YZ عضو L پس کلاسی بنام b معنی نداره در ساختمان گسسته گریمالدی میگه اعضای کلاس b آنهایی هستند که با اضافه کردن هیچ یا هر رشته ای به انتهای b عضو L شوند
بله درسته، با اضافه کردن هیچ چیز به b نمیشه اون رو عضو L کرد و به همین دلیل سرگروه یکی از کلاس های هم ارزیه که همکلاسی هاش رشته هایی هستن که مثل خود b ، نمیتونن عضو L بشن؛ مثل ba,baba,bba,...
صورت سوال رو با هم میخونیم
فرض کنید x=b و y=baba و z هم که گفته هر رشته دلخواه؛ قبول دارید در این صورت x و y هم ارزند؟ چون برای هر z که xz عضو L باشه، yz هم عضو L هست (البته اگر z پیدا میشد اما الآن فرض همیشه اشتباه و استنتاج همیشه صحیح است)
(۰۳ اسفند ۱۳۹۰ ۱۲:۴۸ ق.ظ)cormen نوشته شده توسط: نکته ای راجع به سوال ۵۵:
تمام رشته های گزینه ۲ به b ختم میشوند در صورتیکه رشته ای مانند aaa جز زبان است گزینه ۳ هم رشته تهی را تولید نمیکند گزینه ۴ هم رشته abab را که جز زبان است را نمیتواند تولید کند واضح است که گزینه ۱ جواب نهایی است
این سوال به احتمال قوی حذف میشه، چون ۱ رشته سر امتحان پیدا کردم که تو گزینه ها صدق نمی کرد (:
(۰۷ اسفند ۱۳۹۰ ۰۲:۵۶ ب.ظ)mohammad_13690 نوشته شده توسط: بله درسته، با اضافه کردن هیچ چیز به b نمیشه اون رو عضو L کرد و به همین دلیل سرگروه یکی از کلاس های هم ارزیه که همکلاسی هاش رشته هایی هستن که مثل خود b ، نمیتونن عضو L بشن؛ مثل ba,baba,bba,...
صورت سوال رو با هم میخونیم
فرض کنید x=b و y=baba و z هم که گفته هر رشته دلخواه؛ قبول دارید در این صورت x و y هم ارزند؟ چون برای هر z که xz عضو L باشه، yz هم عضو L هست (البته اگر z پیدا میشد اما الآن فرض همیشه اشتباه و استنتاج همیشه صحیح است)
ogey. سر این تست اکثراً با مفهوم کلاس هم ارزی مشکل داشتند که واقعاً هم حق با اوناست بیشتر به ساختمان گسسته شبیه بود تا نظریه(شاید هم حذف شد).
(۰۷ اسفند ۱۳۹۰ ۰۳:۱۳ ب.ظ)aliebtehaj نوشته شده توسط: ogey. سر این تست اکثراً با مفهوم کلاس هم ارزی مشکل داشتند که واقعاً هم حق با اوناست بیشتر به ساختمان گسسته شبیه بود تا نظریه(شاید هم حذف شد).کاش حذف میشد؛ منم سر جلسه کلاس هم ارزی رو قاطی کردم اشتباه زدم
به نظر شما سوال ۵۳ گزینه ۳ جواب درست نیست،سنجش ۴ زده!!!!!!
(۰۸ اسفند ۱۳۹۰ ۱۲:۰۶ ق.ظ)FARMOKH نوشته شده توسط: به نظر شما سوال ۵۳ گزینه ۳ جواب درست نیست،سنجش ۴ زده!!!!!!
من هم زدم ۴
اما استدلال خاصی ندارم
در مورد سوال ۵۳ گزینه ۳ هم می توانید درست باشد چون مورد اول حتما غلط است و یک قضیه در کتاب پیتر به شمار ۲-۱۱ گفته که زبانهای وجود دارند که بازگشتی برشمردنی نیستد روی الفبای غیر تهی سیکما در نتیجه هر زبان روی سیکما شمارش پذیر نیست و گزینه ۳ هم می تواند درست باشد
(۰۸ اسفند ۱۳۹۰ ۰۵:۵۷ ب.ظ)ehsan.m نوشته شده توسط: در مورد سوال ۵۳ گزینه ۳ هم می توانید درست باشد چون مورد اول حتما غلط است و یک قضیه در کتاب پیتر به شمار ۲-۱۱ گفته که زبانهای وجود دارند که بازگشتی برشمردنی نیستد روی الفبای غیر تهی سیکما در نتیجه هر زبان روی سیکما شمارش پذیر نیست و گزینه ۳ هم می تواند درست باشدموافقم
قضیه ۱۱-۲
به ازای هر سیکما غیر تهی زبانهایی هستند که بازگشتی بر شمردنی نیستند
یک نکته دیگه هم بعد از تعریف ۲-۱۱ امده که میگه اگر زبان بازگشتی باشه انوقت حتما روال بر شمارش برای ان هست
پس الف حتما اشتبایه
حتما اعتراض بزنید
سوال ۵۴ هم می تونه حذف بشه چون کلاس هم ارزی تو کتاب لینز نیست
در مورد سوال ۵۳
به نظر شما زبانی وجود دارد که بشه براش گرامری نوشت اما الگوریتمی براش وجود نداشته باشه؟
وجود گرامر برای تشخیص اینکه زبان تصمیم پذیر هست کافی نیست؟