(۱۱ اسفند ۱۳۸۹ ۰۹:۲۹ ب.ظ)saria نوشته شده توسط: 1 . رشته نمیتونه طولش نامتناهی باشه فرض میکنیم طول رشتمون مثلا K هستش
۲ . مییدونیم هررشته که LL(K باشه حتما مستقل از متن هست
۳ . در نتیجه ما منتونیم رشته اول رو به طور کامل تو پشته بریزیم و موقع ریختن رشته دوم به طور غیر قطعی میریم و اولین حرف رشته اول رو چک میکنیم . اگه با هم برابر بودند که رشته پذیرفته نمیشه اگه برابر نبودند سراغ دومین حرف میریمو.....
درنتیجه گزینه ۱ میشه (وسط رشته یعنی جایی که تشخیص میدیم که رشته دوم داره ریخته میشه بصورت غیر قطعی تشخیص داده میشه)
این نظر رو تو یه تایپیک دیگه مطرح کردم که دوستان به واسطه مقایسه با WW ردش کردن منم پذیرفتم چون علمم بیشتر نمیکشید
این طرز فکر و از استادی پرسیدم و گفتند که این فکر کاملا درسته
همه جملات گفته شده در بالا از کتاب لینز گفته شده
اگه حواستید صفحاتشو میگم
بنظر من قانع کننده بود.مرسی
(۱۱ اسفند ۱۳۸۹ ۰۹:۲۹ ب.ظ)saria نوشته شده توسط: 1 . رشته نمیتونه طولش نامتناهی باشه فرض میکنیم طول رشتمون مثلا K هستش
۲ . مییدونیم هررشته که LL(K باشه حتما مستقل از متن هست
۳ . در نتیجه ما منتونیم رشته اول رو به طور کامل تو پشته بریزیم و موقع ریختن رشته دوم به طور غیر قطعی میریم و اولین حرف رشته اول رو چک میکنیم . اگه با هم برابر بودند که رشته پذیرفته نمیشه اگه برابر نبودند سراغ دومین حرف میریمو.....
درنتیجه گزینه ۱ میشه (وسط رشته یعنی جایی که تشخیص میدیم که رشته دوم داره ریخته میشه بصورت غیر قطعی تشخیص داده میشه)
این نظر رو تو یه تایپیک دیگه مطرح کردم که دوستان به واسطه مقایسه با WW ردش کردن منم پذیرفتم چون علمم بیشتر نمیکشید
این طرز فکر و از استادی پرسیدم و گفتند که این فکر کاملا درسته
همه جملات گفته شده در بالا از کتاب لینز گفته شده
اگه حواستید صفحاتشو میگم
ببخشید ولی من ۲تا مشکل با قسمت سوم دارم ممنون میشم اگه توضیح بدید:
۱) اگه حرف اول برابر باشه رشته پذیرفته نمی شه؟ این که یه حرف تو ۲تا قسمت اول و دوم رشته برابر باشه دلیل بر این نمیشه که کل ۲ قسمت رشته برابر باشن
۲) رشتهی اول رو که در پشته بریزیم حرف اولش در انتهای پشته قرار میگیره و نه در بالای اون شما چه جوری اولین حرف اون رشته رو چک می کنید؟ به نظر کاملا غلط میاد
*البته به نظر من سنجش اشتباه نکرده ولی این اثبات هم درست به نظر نمی رسه
توی جزوه نظریه طرح ۹۰ درصد امسال توی جدول آخر نوشته این زبان مستقل از متن نیست!صفحه ۵۴
تالیغف حاج سید جوادی بوده! اما دلیلشو ننوشته اگر کسی ایمیل حاج سید جوادی را داره ایمیل بزنه!
تمرین شماره ۲۳ عکس ضمیمه را نگاه کنید!
از کتاب Sipser است.
(۱۲ اسفند ۱۳۸۹ ۰۲:۴۴ ب.ظ)۸۷۸۵۵۶۱۱ نوشته شده توسط: تمرین شماره ۲۳ عکس ضمیمه را نگاه کنید!
از کتاب Sipser است.
پس مشخص شد که L1 مستقل از متنه . دوستان به نظرم به جای اینکه تلاش کنید ثابت کنید که مستقل از متن نیست، سعی کنید ثابت کنید که هست . تمرین ۲۳ این کتاب که دوستمون فرمودند دقیقا همون زبانه .
حالا شیطون کتاب Sipser دیگه چه صیغه ایه ؟ من که تا حالا اسمشم نشنیدم.
(۱۲ اسفند ۱۳۸۹ ۰۳:۰۶ ب.ظ)۸۷۸۵۵۶۱۱ نوشته شده توسط:(12 اسفند ۱۳۸۹ ۰۲:۵۸ ب.ظ)hsh88 نوشته شده توسط: جالبه!دقیقا برعکس پارسه!
حل تمرینش را اگه دارید ببینید چه جوریه واسمون بگذارید. مرسیییی
حل نکرده!
دوستان حل تمرینشو پیدا کردم. بالاخره پس از این همه پست( در پست صدم ) این معضل حل شد :
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
پس گرامر مستقل از متن مربوط به زبان L1 تست شماره ۶۲ می شه این:
کد:
S->UV|VU
U->aUa|bUa|aUb|bUb|a
V->aVa|bVa|aVb|bVb|bتو فایل ضمیمه شده هم در صفحه دوم می تونید PDA مربوط به این زبان رو ببینید .
با تشکر از دوست عزیز ۸۷۸۵۵۶۱۱
![[تصویر: 18690_1_1379098561.gif]](https://img.manesht.ir/18690_1_1379098561.gif)
![[تصویر: 18690_2_1379098561.gif]](https://img.manesht.ir/18690_2_1379098561.gif)
![[تصویر: 18690_3_1379098561.gif]](https://img.manesht.ir/18690_3_1379098561.gif)
چه جالب یعنی چون مخالف باید باشن w1,w2 پس فقط کافیه
na(w1)#na(w2)
, nb(w1)#nb(w2 .....
پس این l1 , l2 یه جورایی شبیه هم بودند!
نه فرق دارند مثل abba، مثل اینکه مستقل از متن در اومد البته فعلاً . ممنون از دوستان
بچهها من واقعاً موندم چرا ww پس مستقل از متن در نظر گرفته نمیشه ؟؟؟؟؟ کسی میدونه ؟؟؟؟
ببینید اگه ww باشه مثلا من میگم همون abba خوب؟ این الان تعداد a,b های دو قسمت یکیه ولی ww نیست پس نمیشه از یکی بودن به جایی رسید اما وقتی یکی نباشه حتما ww نیست چون اگه ww باشه حتما یکی است.
یعنی نمیشه که دو طرف مساوی باشن ولی تعداد نمادها یکی نباشه! پس اگه تعداد نمادها یکی نبود حتما یکی نیستن!
اما میشه یکی نباشن ولی تعداد نمادها یکی باشه.پس از برابری نمادها نمیشه نتیجه ای گرفت.
من که نگفتم l1,l2 یکی هستند گفتم شبیه اند منظورم این بود که هردو روی تعداد سمبلها کار میکنند.
با NoOne موافقم . به نظرم طراح نظریه امسال، هم کتاب پارسه( دکتر نورالله )و هم جزوه ۹۰ %( حاج سید جوادی )رو دیده بوده و متوجه این اشتباهشون( البته اشتباهاتشون، چون به نظرم بازم ایراد هست )شده بوده و خواسته با این تست این نکته رو به اونها گوشزد کنه . البته نباید منکر زحمات این دو عزیز شد ولی به هر حال باید دقت بیشتری داشته باشند تا بچهها تو تله های اینچنینی نیفتند. البته خوشبختانه من نیفتادم و سر کنکور با یه استدلال ساده گزینه یک رو زدم . اگه کتاب پارسه ملکه ذهنم بود قطعا اشتباه می زدم. سعی کردم تحلیل کنم ولی انصافا پیدا کردن گرامر واسه این زبان اونم سرکنکور غیرممکنه مگه قبلا جایی دیده باشی .
در مورد کتاب مذکور هم موافقم که بچه های سال بعد این کتاب رو یه منبع مهم واسه درس نظریه بدونند، واسه راحتی شون من لینک دانلود این کتاب رو که ۲۰ مگابایته تو همین پست می ذارم، البته جاش تو آرشیو پیوندهاست ولی خوب اینجا هم خیلی بی ربط نیست .
در مورد کتاب مذکور هم موافقم که بچه های سال بعد این کتاب رو یه منبع مهم واسه درس نظریه بدونند، واسه راحتی شون من لینک دانلود این کتاب رو که ۲۰ مگابایته تو همین پست می ذارم، البته جاش تو آرشیو پیوندهاست ولی خوب اینجا هم خیلی بی ربط نیست .
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
اعتماد به نفس ندارم منم که گفتم به احتمال خیلی زیاد مستقل از متنه (طبق شواهدی که دوستان داشتند)
آخه میدونی چیه من یکم محافظه کارم و یکم به جواب سوالات به خصوص نظریه بدبین .(همیشه امکان این وجود داره که جواب یک چیزه دیگه باشه که شما فکرش نمیکنید )
و دلیل آخرم اینکه سید جوادی، دکتر کارگهی کم کسانی نیستند، آخه همه اینها متفقل قول میگن این زبان مستقل از متن نیست نکنه یک نکته داره که کسی به اون دقت نکرده
ثانیا من هنوز سر ww قانع نشدم . مگه pda یا npda برای این زبان نداریم و اگه دو رشته ای که کاراکترهای آخر یکسانی ندارند جز این زبان است و توسط این زبان پذیرفته میشه درسته ؟! پس چرا نمیتونه ww را تشخیص بده، اصلا حرفهای بالام را بیخیال همین سوال منو جواب بدید.خیلی تو قانع شدنم کمک میکنه (حقیقت آفاق خانم نظر شما را متوجه نشدم یکم واضحتر توضیح میدید)
(۱۲ اسفند ۱۳۸۹ ۰۷:۲۸ ب.ظ)hatami84 نوشته شده توسط: اعتماد به نفس ندارم منم که گفتم به احتمال خیلی زیاد مستقل از متنه (طبق شواهدی که دوستان داشتند)
آخه میدونی چیه من یکم محافظه کارم و یکم به جواب سوالات به خصوص نظریه بدبین .(همیشه امکان این وجود داره که جواب یک چیزه دیگه باشه که شما فکرش نمیکنید )
و دلیل آخرم اینکه سید جوادی، دکتر کارگهی کم کسانی نیستند، آخه همه اینها متفقل قول میگن این زبان مستقل از متن نیست نکنه یک نکته داره که کسی به اون دقت نکرده
ثانیا من هنوز سر ww قانع نشدم . مگه pda یا npda برای این زبان نداریم و اگه دو رشته ای که کاراکترهای آخر یکسانی ندارند جز این زبان است و توسط این زبان پذیرفته میشه درسته ؟! پس چرا نمیتونه ww را تشخیص بده، اصلا حرفهای بالام را بیخیال همین سوال منو جواب بدید.خیلی تو قانع شدنم کمک میکنه (حقیقت آفاق خانم نظر شما را متوجه نشدم یکم واضحتر توضیح میدید)
چیزی که من از حرف شما متوجه شدم اینه که میگید اگه wawb جزو این زبانه و توسط این زبان پذیرفته میشه پس چرا ww رو نمی پذیره؟ اگه اشتباه می کنم لطف کنید و ۲ باره و دقیقتر سوال رو مطرح کنید و اگه سوال رو درست متوجه شدم خب دلیلش اینه که در واقع این گرامر فقط تمرکزش روی اون ۲ تا کاراکتری که قراره متفاوت باشند هستش یعنی بقیه، هم می تونن مساوی باشن هم می تونن نباشن. برای این مثال شما هم گرامر اصلا حواسش به این نیست که رشته های شما wa و wb هستن و حتی اگه [tex]wa[/tex] و [tex]w'b[/tex] هم بودن بازم می پذیرفت.
نمی دونم تونستم منظورم رو برسونم یا نه؟
نه بحث سر کاراکترهای آخر نیست!!
چیزی که من برداشت کردم اینه که میاد تعداد a های w1 رو میشمره تعداد b هاش رو هم همینطور حالا اگه تعداد a های w1 با تعداد a های w2 یکی نبود یا تعداد b هاشون یکی نبود یعنی w1#w2 است.
اما اگه بخوایم بگیم w1=w2 مساوی بودن تعداد نمادها کمکی نمیکنه چون توی abba تعداد نمادهای دو قسمت یکیه ولی خودشون یکی نیستن.
من یکم دیر اومدم و مثل اینکه دارین نتیجه گیری میکنید! بچهها لطفا نظر من رو هم بررسی کنید
اثبات درستی گزینه ۳ به این صورت هست:
در مورد l2 بحثی نیست و هر رشته ای رو بگی تعداد a و b در اون مساویست پس هر رشته ای رو میپذیره و خب منظم میشه.
و اما l1 این زبون قطعا آزاد نیست . فرض کنید شرط w1=w2 بود که سوال (طول هم که یکسان هست!) میشد l1={ww} که آزاد نیست. دوستان هیج فرقی نداره، اگر نتونیم با پشته چک کنیم که برابرند خب نمیتونیمم چک کنیم که برابر نیستند .
ما باید هر دو رشته رو از ابتداشون حرف به حرف چک کنیم و اگه حداقل یک اختلاف پیدا شد یا اگر طولشون یکسان نبود بگیم برابر نیستند و ما بعد از قرار دادن w1 در پشته به ابتداش واسه مقایسه با w2 دسترسی نداریم.
در ضمن برابری طول هم تفاوتی ایجاد نمیکنه.