همون ۲ میشه فکر کنم

ممنون آفاق جان من آخر نظر کلیت در مورد سوال ۶۲ را متوجه نشدم ؟! من خودم زدم گزینه ۳

من از روی بی دقتی ۱ زدم ولی فکر میکنم ۳ درست باشه!

(۳۰ بهمن ۱۳۸۹ ۰۴:۳۴ ب.ظ)hatami84 نوشته شده توسط:  نظرتون در مورد سوال ۵۹ چیه من زدم ۲

سئوال ۵۹ دو نمیشه، مثلاً رشته‌ی aab زیر رشته‌ی ab رو داره ولی به حالت نهایی نمیرسه! آخه مسخره اینه که حالت نهاییش درست معلوم نیست q5 میشه!!!!
من که زدم گزینه‌ی ۴

ادیت: وای من تازه متوجه شدم نوشته هم زیر رشته‌ی ab و هم زیر رشته‌ی ba!!! یعنی باید دوتاشون با هم برقرار باشه!!! وای.... با این حساب همون گزینه‌ی ۲ صحیحه!!!

(۳۰ بهمن ۱۳۸۹ ۰۵:۰۰ ب.ظ)Mansoureh نوشته شده توسط:  

(30 بهمن ۱۳۸۹ ۰۴:۳۴ ب.ظ)hatami84 نوشته شده توسط:  نظرتون در مورد سوال ۵۹ چیه من زدم ۲

سئوال ۵۹ دو نمیشه، مثلاً رشته‌ی aab زیر رشته‌ی ab رو داره ولی به حالت نهایی نمیرسه! آخه مسخره اینه که حالت نهاییش درست معلوم نیست q5 میشه!!!!
من که زدم گزینه‌ی ۴

ادیت: وای من تازه متوجه شدم نوشته هم زیر رشته‌ی ab و هم زیر رشته‌ی ba!!! یعنی باید دوتاشون با هم برقرار باشه!!! وای.... با این حساب همون گزینه‌ی ۲ صحیحه!!!

منم ۵۹ رو ۴ زدم. دقت کنید گ ۲ حالت خاصی از گ۴ هست. یعنی گ۴ ممکنه رسته های گ ۲ رو هم شامل شه و در نتیجه می شه گفت احتمال اینکه این گزینه، گزینه صحیح باشه بیشتره.

هر دو زیر رشته ab,ba رو باید داشته باشه این مثال شما ba نداره که!

منم ۲ زدم

سوال ۶۰ رو چیزدین ؟

من ۲ زدم اما گویا اشتباهه

بچه‌ها شک نکنید اگر حالت ۵ نهایی باشه همون گزینه ۲ هست
هر رشته که مثال بزنین شامل ab , ba هست
و از طرفی رشته ای با این مشخصه نیست که توسط شکل تولید نشه
البته به همون شرط که حالت ۵ رو نهایی بگیریم

۵۸ ۳
۶۰ ۴
۶۱ ۴
۶۲ ۲ نظرتون چیه ؟

(۳۰ بهمن ۱۳۸۹ ۰۵:۱۹ ب.ظ)bahar نوشته شده توسط:  58 3
۶۰ ۴
۶۱ ۴
۶۲ ۲ نظرتون چیه ؟

من ۵۸ و ۶۱ همینای تورو زدم اونای دیگه رو نزدم
بجاش ۵۷ رو ۳
و ۵۹ رو ۲
زدم

منم ۵۹ رو ۲ زدم جلوتر گفتم بچه‌ها بجنبید راستی مدرسان شریف تا ۲ سه روز دیگه توسایتش زده که پاسخنامه رو میزنه راست ودروغش با خودشون
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

سلام دوستان..
میخواستم نظرمو درباره سوال ۶۱ بگم.
به نظر من گزینه ۳ میشه
درباره W1‌ :

S => acBdeA => ac(aSb)deA => aca(acBdeA)bdeA => acaac(aSb)deAbdeA => acaaca(BAB)bdeAbdeA => acaaca(AB)bdeAbdeA => acaaca(B)bdeAbdeA => acaacabbdeAbdeA => acaacabbdebdeA => acaacabbdebdeb

اگر مشکلی داشت بگید.

درباره W2‌:

من نمیتونم ۲ تا e یعنی (ee) رو پشت سر هم تولید کنم.

(۳۰ بهمن ۱۳۸۹ ۰۵:۵۵ ب.ظ)khoofi66 نوشته شده توسط:  سلام دوستان..
میخواستم نظرمو درباره سوال ۶۱ بگم.
به نظر من گزینه ۳ میشه
درباره W1‌ :

S => acBdeA => ac(aSb)deA => aca(acBdeA)bdeA => acaac(aSb)deAbdeA => acaaca(BAB)bdeAbdeA => acaaca(AB)bdeAbdeA => acaaca(B)bdeAbdeA => acaacabbdeAbdeA => acaacabbdebdeA => acaacabbdebdeb

اگر مشکلی داشت بگید.

درباره W2‌:

من نمیتونم ۲ تا e یعنی (ee) رو پشت سر هم تولید کنم.

آفرین من هم همین نظرت رو دارم! w1 قابل قبوله و میشه تولیدش کرد و w2 با همون دلیلت رد میشه

(۳۰ بهمن ۱۳۸۹ ۰۵:۵۵ ب.ظ)khoofi66 نوشته شده توسط:  سلام دوستان..
میخواستم نظرمو درباره سوال ۶۱ بگم.
به نظر من گزینه ۳ میشه
درباره W1‌ :

S => acBdeA => ac(aSb)deA => aca(acBdeA)bdeA => acaac(aSb)deAbdeA => acaaca(BAB)bdeAbdeA => acaaca(AB)bdeAbdeA => acaaca(B)bdeAbdeA => acaacabbdeAbdeA => acaacabbdebdeA => acaacabbdebdeb

اگر مشکلی داشت بگید.
حق با لینز می باشد
درباره W2‌:

من نمیتونم ۲ تا e یعنی (ee) رو پشت سر هم تولید کنم.

حق با شماست
اگه میشه کد سوالاتونو بگین
A
B
C
D
یا به سوال اشاره کنید

---

(۰۱ اسفند ۱۳۸۹ ۰۸:۱۴ ق.ظ)shahryar نوشته شده توسط:  

(01 اسفند ۱۳۸۹ ۰۱:۰۱ ق.ظ)hatami84 نوشته شده توسط:  

(01 اسفند ۱۳۸۹ ۱۲:۰۷ ق.ظ)shahryar نوشته شده توسط:  پارسه w1cw2 رو هم گفته مستقل از متن نیست!
در حالی که لینز گفته هست.

اگه طول رشته‌ها با هم برابر نباشه صد در صد مستقل از متن است
ولی اگه طول رشته‌ها با هم بخواد مساوی باشه مستقل از متن نیست

منم دارم راجع به نامساوی حرف می زنم.
منم می دونم آزاد از متنه!
ولی می گم پارسه گفته نیست.

کمی روی ویژگی های بستاری زبان های مستقل از متن مانور بدین
متمم
اشتراک و.....

من سئوال ۶۲ رو گزینه‌ی ۳ زدم!!!
گزینه‌ی ۱ که مستقل از متن نیست!!!
گزینه‌ی دو هم مستقل از متن غیر قطعی است! یعنی باید غیر قطعی فکر کنیم!!! گزینه‌ی یک هم به دلیل اینکه وسط رشته معلوم نیست نمیشه نظری درباره اش داد...

سوال ۵۸-۳
۵۹-۲
۶۱-۳
۶۲-۳
بقیه نظریه رو هم نزدم.

من نظرمو راجع به سوال ۶۲ میگم اگه کسی اشکال تو استدلالم داش بگه
رشته نمیتونه طولش نامتناهی باشه فرض میکنیم طول رشتمون مثلا K هستش
مییدونیم هررشته که LL(K باشه حتما مستقل از متن هست
در نتیجه ما منتونیم رشته اول رو به طور کامل تو پشته بریزیم و موقع ریختن رشته دوم به طور غیر قطعی میریم و اولین حرف رشته اول رو چک میکنیم . اگه با هم برابر بودند که رشته پذیرفته نمیشه اگه برابر نبودند سراغ دومین حرف میریمو.....
درنتیجه گزینه ۱ میشه
این استدلال کجاش مشکل داره؟؟

(۳۰ بهمن ۱۳۸۹ ۱۰:۲۵ ب.ظ)saria نوشته شده توسط:  من نظرمو راجع به سوال ۶۲ میگم اگه کسی اشکال تو استدلالم داش بگه
رشته نمیتونه طولش نامتناهی باشه فرض میکنیم طول رشتمون مثلا K هستش
مییدونیم هررشته که LL(K باشه حتما مستقل از متن هست
در نتیجه ما منتونیم رشته اول رو به طور کامل تو پشته بریزیم و موقع ریختن رشته دوم به طور غیر قطعی میریم و اولین حرف رشته اول رو چک میکنیم . اگه با هم برابر بودند که رشته پذیرفته نمیشه اگه برابر نبودند سراغ دومین حرف میریمو.....
درنتیجه گزینه ۱ میشه
این استدلال کجاش مشکل داره؟؟

ماشین تورینگ که نیست پشته است چه جوری میخوای از وسط رشته بری اول رشته رو چک کنی؟!

(۳۰ بهمن ۱۳۸۹ ۱۱:۰۵ ب.ظ)afagh1389 نوشته شده توسط:  ماشین تورینگ که نیست پشته است چه جوری میخوای از وسط رشته بری اول رشته رو چک کنی؟!

خوب چرا نمیتونیم وسط رشته رو به صورت غیر قطعی تشخیص بدیم؟

این کمکی به ما نمیکنه شما وقتی WW رو نمیتونی تشخیص بدی این زبان رو هم نمیتونی

(۳۰ بهمن ۱۳۸۹ ۱۱:۲۹ ب.ظ)afagh1389 نوشته شده توسط:  این کمکی به ما نمیکنه شما وقتی WW رو نمیتونی تشخیص بدی این زبان رو هم نمیتونی

اره راس میگی فرقی نمیکنه که بخوایم مساوی بودنشو چک کنیم یا غیر مساوی بودنشو
چه !!!!!!!!!!!!!۱

سوال۶۲ زبان L1 درتمرینای فصل ۹ بخش ۲ (فصل تورینگ) کتاب پیتر لینز مطرح شده و در حل اون باید دو شرط رو با هم and کنیم یکی باید رشته های W1 و W2 باهم مخالف باشه و شرط دیگه هم طول رشته باید زوج باشه که با یک پشته نمیشه دو شرط رو با هم چک کرد

l2 منظمه

شما هر رشته ای که بدی عضو زبان l2 میشه
مثلا من w=aaaaaa رو هم میگم عضو زبانه چون w1=lambda و w2=aaaaaa
اگه شک داری یه رشته بگو که عضو زبان نباشه !

پارسه w1cw2 رو هم گفته مستقل از متن نیست!
در حالی که لینز گفته هست.

(۰۱ اسفند ۱۳۸۹ ۱۲:۰۷ ق.ظ)shahryar نوشته شده توسط:  پارسه w1cw2 رو هم گفته مستقل از متن نیست!
در حالی که لینز گفته هست.

اگه طول رشته‌ها با هم برابر نباشه صد در صد مستقل از متن است
ولی اگه طول رشته‌ها با هم بخواد مساوی باشه مستقل از متن نیست

بله نیست چون محتوای کف پشته رو نمیشه با وسط پشته چک کرد!

افاق خانم همین رشته ای که خودتون مثال زدید عضو زبان نیست

هست دیگه na(landa)=0 nb(aaaaaa)=0 پس رشته عضو زبانه.

آره درسته خیلی جالب بود مثلا رشته abbba عضو زبان نیست

w1=abb
w2=ba

چرا سوال ۶۰ ۲ نمیشه؟

من که الان حل کردم دیدم سوال ۶۱ w1 عضو زبانه منم اشتباه زدم اما هنوز میگم ۶۲ ۲ درست در مورد سوال ۶۰ کسی نظری نداره ؟

ببخشیدا بعد از این همه توضیح شما میگین ۶۲‌، ۲ درسته ؟!!!
تو رو خدا این توضیحاتی که دادم رو بخونید باور کنید این زبان منظمه اونوقت چطور مستقل از متن نیست؟!!

سوال ۶۰ رو من زدم ۲/ چیزی که واضحه اینه که زبان قطعا نامتناهی نیست‌، چون نمی تونه feedback داشته باشه . پس ۳ و ۴ غلطه . حالا اگه کسی بتونه یه گرامری با این ویژگی مثال بزنه که زبانش منظم نباشه‌، اون وقت گزینه ۱ درسته .

PARSANA منم زدم منظمه منم گفتم چون نمیتونه بیش از یک مرحله بازگشت کنه. مثلا اگه از A رفت به B دیگه نمیتونه برگرده به A پس متناهیه و هر زبان متناهی هم منظمه.

وقتی بازگشت نداریم پس نمیتونه نامتناهی باشه چون تعداد قوانین ما محدوده!!

ببینید بی پایان منظورش اینه که ما عناصر پایانی نداریم پارسر پس از یه مدتی اعلام میکنه که چیزی نمیتونم تولید کنم که مجموعه‌ی تهی رو برمیگردونه ولی نامتناهی پارسر رشته های زیادی رو تولید میکنه و پس از یه مدتی میگه بابا خسته شدم..
پس نامتناهی با بی پایان کاملا با هم متفاوته.

اونوقت کجا گفته ما عناصر پایانی نداریم؟!!
اونوقت این چه منظمیه که عناصر پایانی نداره!!!

منم میگم منظمه اما به هیچ پایانه ای ختم نمیشه چطور میگید متناهی درسته که بر نمیگرده اما تو satisfy یک یا چند مرحله به این رسیده من ۴ زدم چون احساس کردم satisfy شده پس برمیگرده ؟

(۰۱ اسفند ۱۳۸۹ ۱۱:۰۴ ق.ظ)bahar نوشته شده توسط:  منم میگم منظمه اما به هیچ پایانه ای ختم نمیشه چطور میگید متناهی درسته که بر نمیگرده اما تو satisfy یک یا چند مرحله به این رسیده من ۴ زدم چون احساس کردم satisfy شده پس برمیگرده ؟

حرف های عجیب می زنیدا . از کجای اون شرط این برداشت رو کردید که گرامر به هیچ پایانه ای ختم نمی شه . مثلا گرامر زیر:
S->A
A->b
آیا این گرامر اون شرط رو نداره‌، آیا نتونسته پایانی تولید کنه . معنی اون شرط اینه که هیچ غیر پایانه ای در گرامر در ۱ یا بیشتر مرحله اشتقاق هرگز به خودش نمی رسد . با همین گرامر بالا می بینید که نمی شه حکم قطعی در مورد بی پایان بودن گرامر دارد.

(۰۱ اسفند ۱۳۸۹ ۱۱:۰۶ ق.ظ)afagh1389 نوشته شده توسط:  اینکه A--->b چه مشکلی داره؟!!
اتفاقا به نظر من خیلی زود پایان می پذیره چون بازگشت نداره و سریع سمبل های پایانی جایگزین قواعد میشن.

---

نمیشه سوالا رو بدین به دکتر قدسی زحمت حلشو بکشن؟!!؟

قدسی استاد همه درس‌ها نیست که‌!

اینکه A--->b چه مشکلی داره؟!!
اتفاقا به نظر من خیلی زود پایان می پذیره چون بازگشت نداره و سریع سمبل های پایانی جایگزین قواعد میشن.

---

نمیشه سوالا رو بدین به دکتر قدسی زحمت حلشو بکشن؟!!؟

پس در نهایت به منظم بودن آن شکی نیست اما بین ۲ گزینه ۲ و ۴ نظر دوستان دیگه هم مهمه ///؟

حل سوال ۶۰ نظریه زبان بر طبق کتاب پیتر لینز صفحه ۲۱۸-تئوری ۸/۷:
جملات دقیقا کلمه به کلمه به فارسی ترجمه شده است:
ما فرض می کنیم که G شامل هیچ کدام از قواعد لاندا-یکه و متغیر های مفید نیست. فرض می کنیم گرامر دارای یه متغیر تکرار شونده در قاعده خود است به طوریکه A متعلق به V (مجموعه غیر پایانی ها) است که برای آن یک اشتقاق وجود دارد.
وقتی فرض شده است که G هیچ قاعده لاندا-یکه و متغیر مفیدی ندارد پس x, y نمی توانند به طور همزمان تهی باشند. وقتی A هیچ متغیر nullable و یا متغیر مفید نیست پس ما داریم:
S=>uAv=>w و
A=>z
در اینجا u,v,z متعلق به T (مجموعه ترمینال یا پایانی) هستند. اما بنابراین:
S=>uAv=>ux^nAy^nv=>ux^nzy^n
و این برای تمامی n قابل قبول و امکان پذیر است بنابراین زبان G نامتناهی(بی پایان) است.
===
در ادامه پیتر لینز طریقه اصلاح چنین گرامری را توضیح داده.
اما بر می گردیم به سوال حالا گزینه های ۳ و ۴ با قسمت اول گفته آقای لینز برابر هستند. اما:
۱- همگی می دانیم زبانی منظم است که برای پذیرش آن بتوانیم یک FA طراحی کنیم(رجوع به کتاب لینز)
۲- گرامر سوال یک گرامر خطی است و می دانیم یک گرامر منظم همیشه خطی است ولی همه گرامر های خطی که منظم نیستند(رجوع به کتاب لینز)
۳- زبان منظم (نوع ۳) زبانی است که گرامر منظم داشته باشد یعنی یا خطی از راست یا خطی از چپ باشد.(رجوع به کتاب لینز)
۴- تعریف نامتناهی: یعنی از حالت شروع که حرکت کردیم حلقه داشته باشد به طوریکه از حالت شروع به آن راهی باشد و از آن به حالت نهایی راهی نباشد.
پس با توجه به نکات فوق گزینه ۳ یعنی زبان معادل آن بی پایان و نامنظم است صحیح است.

(۰۲ اسفند ۱۳۸۹ ۰۲:۰۸ ق.ظ)sdcsada نوشته شده توسط:  حل سوال ۶۰ نظریه زبان بر طبق کتاب پیتر لینز صفحه ۲۱۸-تئوری ۸/۷:
جملات دقیقا کلمه به کلمه به فارسی ترجمه شده است:
ما فرض می کنیم که G شامل هیچ کدام از قواعد لاندا-یکه و متغیر های مفید نیست. فرض می کنیم گرامر دارای یه متغیر تکرار شونده در قاعده خود است به طوریکه A متعلق به V (مجموعه غیر پایانی ها) است که برای آن یک اشتقاق وجود دارد.
وقتی فرض شده است که G هیچ قاعده لاندا-یکه و متغیر مفیدی ندارد پس x, y نمی توانند به طور همزمان تهی باشند. وقتی A هیچ متغیر nullable و یا متغیر مفید نیست پس ما داریم:
S=>uAv=>w و
A=>z
در اینجا u,v,z متعلق به T (مجموعه ترمینال یا پایانی) هستند. اما بنابراین:
S=>uAv=>ux^nAy^nv=>ux^nzy^n
و این برای تمامی n قابل قبول و امکان پذیر است بنابراین زبان G نامتناهی(بی پایان) است.
===
در ادامه پیتر لینز طریقه اصلاح چنین گرامری را توضیح داده.
اما بر می گردیم به سوال حالا گزینه های ۳ و ۴ با قسمت اول گفته آقای لینز برابر هستند. اما:
۱- همگی می دانیم زبانی منظم است که برای پذیرش آن بتوانیم یک FA طراحی کنیم(رجوع به کتاب لینز)
۲- گرامر سوال یک گرامر خطی است و می دانیم یک گرامر منظم همیشه خطی است ولی همه گرامر های خطی که منظم نیستند(رجوع به کتاب لینز)
۳- زبان منظم (نوع ۳) زبانی است که گرامر منظم داشته باشد یعنی یا خطی از راست یا خطی از چپ باشد.(رجوع به کتاب لینز)
۴- تعریف نامتناهی: یعنی از حالت شروع که حرکت کردیم حلقه داشته باشد به طوریکه از حالت شروع به آن راهی باشد و از آن به حالت نهایی راهی نباشد.
پس با توجه به نکات فوق گزینه ۳ یعنی زبان معادل آن بی پایان و نامنظم است صحیح است.

زبان نامنظم هست(هر چند کمی ابهام وجود داره،چون در مورد اینکه متغیر‌ها کجای قواعد میتونه قرار بگیره مطلبی گفته نشده)،اما مطمئنا بی پایان نیست!چون شزط نامتناهی بودن اینه که قسمتی از گرامر دارای بازگشتی باشه(حالا چه مستقیم چه غیر مستقیم)،که شرط تعیین شده وجود بازگشت رو قانونی نمیدونه!

ویرایش‌: در هر صورت چون بازگشتی بودنا قانونی نمیدونه،فرقی نمیکنه کجای گرامر متغیر بیاد،بنابراین منظمه!

آخه گفته که زبان مستقل از متن است وهر زبان منظمی میتونه مستقل از متن باشه

بله قبول دارم که هر زبان منظمی مستقل از متن است اما آیا هر زبان مستقل از متنی هم منظم است در ضمن این توضیحاتی که گفتم مربوط به بخش خصوصیات زبان های مستقل از متن از کتاب لینز بود لطفا به کتاب صفحه ۲۱۸ تئوری ۸/۷ مراجعه کنید و یا عکس زمینه را دانلود کنید.این زبان اصلا منظم نیست.

دقت کنید که سوال دقیقا گفته ما متغیر تکراری نداریم و این یعنی متناهی بودن.

لطفا به بخشی که در کتاب گفتم مراجعه کنید.متغیر A تکرار شونده(خودگردان) است چون در قاعده خود خودش را صدا زده است و یک حلقه بوجود می آید جدای از اینکه u,v چه می خواهند باشند A تکرار شونده است مثلا S=>aSb.در ضمن این مطالب را من از خودم که نمی گم عینا در کتاب لینز این موضوع بحث شده.(رجوع به کتاب لینز-فصل خصوصیات گرامر های و زبان های مستقل از متن-ص۲۸۱-تئوری ۸/۷ و یا عکس ضمینه را دانلود و نگاه کنید.

ببینید من به کتاب مراجعه کردم و اونو خوندم قضیه برای اثبات متناهی بودن یا متناهی نبودن یه گرامر مستقل از متنه خوب تو سوال هم گفته هیچ متغیری تکراری نباشه شما یه بار سوال رو خوب بخون گفته قوانین بازگشتی نداریم و گفته هیچ یک از غیر پایانی‌ها شرط A==>uAv رو نباید داشته باشه

متاسفانه دوستان در مورد سوال ۶۰ نظرات متفاوتی میدن و نمی شه نتیجه گیری کرد.
دوستان ابتدا به ساکن بگید که آیا زبان یک گرامر با چنین شرایطی متناهی است یا نا متناهی؟
متناهی بودنش تا حدودی ملموسه، چون هیچ سمبلی بازگشت نداره. مگر این که خلافش دقیقا اثبات بشه (مثلا مثال نقض) یعنی یه گرامری بگید که بازگشت نداشته باشه ولی نامتناهی باشه. فعلا کاری با خطی و غیر خطی و ... نداریم.
اگر یک زبان متناهی باشه، منظمه، حالا گرامرش هر شکلی که می خواد داشته باشه.
ضمنا توجه کنید که اگر یک زبان نامنظم باشه حتما نامتناهی خواهد بود. (که در این صورت گزینه ۱ و گزینه ۴ دفترچه ۴۰۵A عین هم خواهند بود.)
اگر نامتناهی بود برای گزینه های دیگه دلیل بیارید.
ممنون

نظر منم اینه که چون متناهی است پس منظمه.
ممنون psps جان

من این سوال را نزدم ولی نظرم اینه که این زبان متناهی خواهد بود و چون متناهی است پس منظم است

من هم نظرم همینه ۶۱ گزینه ۳ میشه چون e دوم را نمی تونیم به دست بیاریم