(۲۱ بهمن ۱۳۹۱ ۱۱:۲۴ ب.ظ)arta.66 نوشته شده توسط:(21 بهمن ۱۳۹۱ ۰۳:۴۱ ب.ظ)somaye_tex نوشته شده توسط: منم ارجاع میدم به جزوه دکتر کارگهی که برای این مسأله گرامر مستقل از متن دادن. و البته این سؤال تکراری هم بود. صد در صد ۳ !خوب دیگه اشتباه شما همینه توو کتابای تستی که من دیدم هیچ کدوم این زبانو مستقل از متن نمی دونن - علاوه بر این من یه چی میگم اگه قانع شدین که هیچ اگه نشدین منتظر کلید میشیم-هم دکتر نورالله هم دکتر سیدجوادی این زبانو غیر مستقل از متن میدونن و دلیلشم واضحه- شما چطور میتونی ۲ تا رشته که هیچ اطلاعی از ترتیبش نداریو با یه چشته چک کنی؟؟ مگه نه اینکه رشته از اول خونده میشه میره جلو!! حالا گیریم نقطه انفصال ۲ رشته رم میدونیم و سوال طول ۲ رشترم برابر گذاشته توو شرطش که نذاشته ولی با همین شرطم وقتی به اول رشته دوم میرسی چطوری میخوای با اول رشته اول که ته پشته پوش شده مقایسش کنی؟؟؟ اگه بازم قانع نشدی منتظر کلید باش!! اگه حرفی که در مورد جزوه کارگهی زدی درست باشه تنها امیدت این باشه که طراح خودش بوده باشه و جواب شمارو توو کلید بذاره که در این صورتم باید به دکتر جایزه نوبل بدن واسه کشف جدیدش!!! آها تا یادم نرفته راست میگین این زبانی که روش بحث می کنیم یبار توو کنکورای اخیر اومده و فقط توو کلید اولیه مستقل از متن گفته بودنش که توو اصلاحیه درستش کردنعجب کلی !
اولاً این اساتیدی که فرمودین اگه چزوه هاشون رو با دقت مطالعه کنید متوجه میشید این تنها اشتباهشون نیست و اشتباهات دیگری هم داشتن و اصلاً نمی تونن به عنوان مرجع این درس باشند....
بگذریم.
دوتاشون هم اشتباه می کنن! صد در صد این زبان مستقل از متن غیر قطعیه! یعنی اگه نباشه کلاً مهندسی کامپیوتر و می بوسم و میذارم کنار!
با توجه به اصل عدم قطعیت عدم تساوی قابل تشخیص است . (بر عکس تساوی که قابل تشخیص نیست!) به voice استاد کارگهی رجوع کنید خیلی عالی توضیح دادن. در ضمن که این سؤال تکراریه و حتی در اون سال هم این زبان مستقل از متن غیر قطعی در نظر گرفته شده....
من آنچه شرط بلاغ است با تو می گویم تو خواه از سخنم پنــد گیر خواه ملال
(۲۲ بهمن ۱۳۹۱ ۰۲:۰۸ ب.ظ)مهمد نوشته شده توسط: ببینید اون سوال ۵۷ قسمت نامساویش نه تنها مستقل از متن بلکه منزم هم هست. چون وقتی x نامساوی y باشه زبان، زیگما پلاس هست. شما هر رشته ای که در نزر بگیرید، من میگم x رو لامبدا میگیرم و رشته رو y ، پس تمام رشته ها به جز لامبدا جز زبان هستند.
فکر کنم خیلی بد گفتم، ولی همینکه شما هر رشته ای رو در نزر بگیرید میشه از یه جایی شکوندش و قسمت اول رو x و قسمت دوم رو y در نزر گرفت. یه جوری هم میشکنیم که قسمت اول و دوم عین هم نباشند. موفق باشید
اوه ! من دقت نکرده بودم که تتساوی طول ها رو هم نگفته ! اگه گفته بود طول ها مساوی باشه اما خودشون نامساوی می شد صحبت بالا اما حالا که تساوی طول هاشون رو نگفته میشه منظم...
با تشکر از آقای مهمد.
عجب بی دقتیم من!
دوست عزیز این وسط اگه یه مثال نقض بیاد گزینه غلط میشه شما برا یه حالت منحصر به فرد در نظر بگیر x=a^n b^n+1 و y=a^n b^n حالا به نظر شما این زبان مستقل از متنه؟
(۲۲ بهمن ۱۳۹۱ ۰۲:۰۸ ب.ظ)مهمد نوشته شده توسط:(22 بهمن ۱۳۹۱ ۱۲:۴۳ ب.ظ)arta.66 نوشته شده توسط:(22 بهمن ۱۳۹۱ ۰۱:۲۸ ق.ظ)rezareza2 نوشته شده توسط: سوال ۵۷ گزینه درست ۳ هست. اون حالت نامساوی رو براحتی میتونید با یک اوماتای پشته ای نامعین چک کنید.من ترجیح میدم تحلیلی که گفتم و منطقم ام قبولش داره رو باور کنم تا یه جواب کلی حفظی رو !! تازه اگه حفظی ام بخوام قبول کنم الان کتاب پارسه جلوم بازه و اون زبانو مستقل از متن نمیدونه!! نه تنها اونو بلکه حالتی ام که توو شرط طول ۲ رشته رو برابر میدونه رم مستقل از متن نمیدونه!!
ببینید اون سوال ۵۷ قسمت نامساویش نه تنها مستقل از متن بلکه منزم هم هست. چون وقتی x نامساوی y باشه زبان، زیگما پلاس هست. شما هر رشته ای که در نزر بگیرید، من میگم x رو لامبدا میگیرم و رشته رو y ، پس تمام رشته ها به جز لامبدا جز زبان هستند.
فکر کنم خیلی بد گفتم، ولی همینکه شما هر رشته ای رو در نزر بگیرید میشه از یه جایی شکوندش و قسمت اول رو x و قسمت دوم رو y در نزر گرفت. یه جوری هم میشکنیم که قسمت اول و دوم عین هم نباشند. موفق باشید
آقا مهمد ، اگه اینطوری که شما گفتیم بخوایم در نظر بگیریم که اکثر زبانهای موجود رو میتونیم منظم در نظر بگیریم.
در حالت نامساوی ، زیر مجموعه زیگما پلاس رو خواهیم داشت نه خود زیگما پلاس. در اینجا تاکید داره که رشته اول حتما" مخالف رشته دوم باشه ولی توضیحات شما کل حالات موجود رو در بر میگیره چه مخالف و چه مساوی .
بنابر این حتی با فرض درستی استدلال شما، تنها گزینه ای که حتما" غلط خواهد بود گزینه ۳ (L با محدودیتهای II ,III,IV مستقل از متن است و با I نیست) است .چون طریقه تشخیص مساوی بودن یا عدم تساوی دو رشته کاملا شبیه به هم است پس هر دو حالت با هم یا باید مستقل از متن باشن یا هر دو مستقل از متن نباشند.
در مورد سوال ۵۵ هم فکر میکنم PDA داده شده فقط تعداد فرد a رو قبول میکنه و چون در صورت سوال نگفته که گرامر این PDA ، کدام نیست ، بلکه گفته توسط کدام گرامر تولید نمیگردند . یعنی میتونه دقیقا" گرامر این ماشین نباشه ولی بتونه تمام رشته های مورد قبولش رو تولید کنه. پس باید دنبال گزینه ای بگردیم که نتونه تمام a های فرد رو تولید کنه . گزینه های ۲ و ۴ که a های فرد تولید میکنن جواب نخواهند بود . گزنه ۳ چون تمام a ها (چه فرد و چه زوج )را تولید میکند پس قادر به تولید a های فرد نیز است و بنابراین جوای نخواهد بود . اما گزینه ۱ چون aaa را به عنوان مثال تولید نمیکند پس نمیتواند زبان PDA را تولید کند ( نه اینکه زبانش باشد ) پس جواب گزینه۱ باید باشد. ( این نظر منه و شاید هم اشتباه میکنم)
من خودم رو این ۵۵ شک داشتم بعد که تو خونه فکر کردم به این نتیجه که عرض کردم رسیدم . تا ببینیم نظر اساتید چیه.
خوب اینطوری گرامر اولی هم میتونه تعدادفرد a رو تولید کنه به دقت جا گذاری کنید متوجه میشید
گزینه اول همه ی فردها رو تولید نمیکنه، داره ۳n+1 تا a میسازه
گزینه ۳ a* میسازه، رشته aaa رو هم به شکل زیر تولید میکنه:
S
aaB
aaaB
aaaaB
aaa
متاسفانه من هم گزینه ۳ رو زدم... اما کاملا مشخصه که جواب گزینه ۱ و نظر faryou کاملا درست هست.
حق با شماست دوست خوبم.
الان یکبار دیگه بررسی کردم دیدم درست می فرمایید.
گزینه ۱
aBaa
aSaa
aaBaaaa
حالا کافیه به جای aB اپسیلون بزاریم که میشه
aaaaa
که تعداد فرد a میشه امنحان کن دوست من ببین همین میشه یا نه اصلا ما میتونیم هر سری واسه تولید تعداد فرد a از این قاعده استفاده کنیم
کدومش damavand_kellap جان ؟
برای aaa رو که امتحان کنی تنها گزینه ای که نمیتونه اینو درست تولید کنه گزینه ۱ هست.
درمورد سوال ۵۵ نظریه که دو تا گزینه صحیح هست چه اتفاقی می افته؟
هر کدوم از دو گزینه زده بشه درست درنظر گرفته میشه؟
بچه ها سوال ۵۵ رو چی زدید ؟
من هنوز فکر میکنم سوال ماشین تورینگ اشتباه باشه،وقتی ورودی رو بشکل x=11 و y=1 بدید ( درواقع رشته ورودی ۱۱۰۱) جوابی که در میاد ۱۱۱۱ میشه،این در هیچ کدوم از گزینه ها صدق نمیکنه !!
نظر دوستان چیه ؟
(۲۴ بهمن ۱۳۹۱ ۱۲:۳۷ ب.ظ)rezareza2 نوشته شده توسط: بچه ها سوال ۵۵ رو چی زدید ؟
من هنوز فکر میکنم سوال ماشین تورینگ اشتباه باشه،وقتی ورودی رو بشکل x=11 و y=1 بدید ( درواقع رشته ورودی ۱۱۰۱) جوابی که در میاد ۱۱۱۱ میشه،این در هیچ کدوم از گزینه ها صدق نمیکنه !!
نظر دوستان چیه ؟
توگزینه ۱ صدق میکنه دیگه،x=2 و y=1.
باقیمانده ۱ بر ۲=۱که جمع این مقدار با x+1برابر ۴ میشه،همون چیزی که خودتون به دست آوردین.
وای بر من!!!!!
اینقدر تو فکر این ۰ و ۱ بودم باینری در نظر گرفتم!!!!!!!!!!!!!!
(۲۱ بهمن ۱۳۹۱ ۰۱:۱۹ ب.ظ)azad_ahmadi نوشته شده توسط: سوال اولش راخت بود. زبانی که نتونه تعداد a رو بصورت ۲k یا زوج بدست بیاره. همین.سلام در مورد سوالی که از سال نود بود منم با شما موافقم ولی مثل اینکه بچه ها چیز دیگه ای مد نظرشونه
یه سوال تکراری از ۹۰ هم داده بودن، هر رشته ای شامل زیر رشته aba یا bab میشه، یه همچین چیزی. اون بود.
سوال تورینگ هم میشه x +1 + (y mod 2 صد در هزار مطمئنم.(البته یه مقدار شک دارم)
اما همه ۱هارو مینویسه، صفر بین ۲رشته رو یک میکنه، هرتعداد یک بعد از صفر رو صفر میکنه، بعد هر صفر رو بلاک میکنه. اگه تعداد یک های بعداز صفر زوج باشن ۰ ۲ ۴ ۶ به همون صورت خارج میشه، اما اگه فرد باشن ۱ ۳ ۵ ۷ یک بلاک رو به ۱ تبدیل می کنه. همین.
(۲۴ بهمن ۱۳۹۱ ۰۶:۴۳ ب.ظ)۱۲۳aaa نوشته شده توسط:(21 بهمن ۱۳۹۱ ۰۱:۱۹ ب.ظ)azad_ahmadi نوشته شده توسط: سوال اولش راخت بود. زبانی که نتونه تعداد a رو بصورت ۲k یا زوج بدست بیاره. همین.سلام در مورد سوالی که از سال نود بود منم با شما موافقم ولی مثل اینکه بچه ها چیز دیگه ای مد نظرشونه
یه سوال تکراری از ۹۰ هم داده بودن، هر رشته ای شامل زیر رشته aba یا bab میشه، یه همچین چیزی. اون بود.
سوال تورینگ هم میشه x +1 + (y mod 2 صد در هزار مطمئنم.
اما همه ۱هارو مینویسه، صفر بین ۲رشته رو یک میکنه، هرتعداد یک بعد از صفر رو صفر میکنه، بعد هر صفر رو بلاک میکنه. اگه تعداد یک های بعداز صفر زوج باشن ۰ ۲ ۴ ۶ به همون صورت خارج میشه، اما اگه فرد باشن ۱ ۳ ۵ ۷ یک بلاک رو به ۱ تبدیل می کنه. همین.
در مورد سوال ۹۰ معلومه ۴ چون کوچکترین رشته aba که هم شامل زیر شته ab و هم ba و bab که باز هم شامل زیر شته ab و هم ba است.
راجع به سوال ۵۷ :
وقتی x=y اومده یعنی نمیشه با پشته تشخیص داد . این زبان مستقل از متن نیست با این محدودیت .
x<>y هم مثل اینه که بخوای بررسی کنی که x=y هست یا نه که باز هم مستقل از متن نیست .
اما با محدودیت های x=yR و تعداد حروف x و y برابر نباشه مستقل از متن هست .
پس میشه گزینه ۱
در مورد سوال ۵۳ :
مسیر بالا رشته هایی رو تولید میکنه که با a شروع میشن و در ادامه تا دیدن یک b هی a رد میکنه و بعد از دیدن حداقل یک b با یک a تموم میشه پس هم ab داره هم ba
برای مسیر پایین دقیقا همینه فقط با b شروع میشه .
پس میشه گزینه ۴
در مورد سوال ۵۵ :
ماشین رشته هایی رو میپذیره که تعداد فردی a داشته باشند. که گرامر گزینه ۱ یک رشته با طول زوج ۲ تولید میکنه .
s->aBaa->aa
پس میشه گزینه ۱
در مورد سوال ۵۶ :
L2 اشتراکش با L3 میشه خود L2 که نمیشه با پشته ای تشخیصش داد .
به نظر من میشه گزینه ۱
چون گزینه ۴ میشه اجتماع L1 و L2 که میشه خود L1 که فقط کافیه شما هر چی اومد رد کنی و تو پشته چیزی ننویسی. پس هر رشته ای بیاد پذیرفته میشه.