۵۷ گزینه ۳ می شه دکتر کارگهی کاملا گفته که چرا x=/y را می شه براش زبان مستقل از متن انم ازنوع غیر قطعی نوشت
(۲۵ بهمن ۱۳۹۱ ۱۱:۵۷ ق.ظ)Nima Masghadi نوشته شده توسط: راجع به سوال ۵۷ :من خودم این تستو زدم گزینه ۳ البته بخاطر کتاب مدرسان و پارسه ولی بعد کلی بحث با دوستان به این نتیجه رسیدم که مستقل از متنه ولی بازم واسه اطمینان رفتم سراغ کتاب لینز !! دقیقا یکی از تمریناشه که واسش جوابم گذاشته ته کتاب ! با اونکه ماشینشو رسم نکرده ولی گفته در کمال تعجب این زبان مستقل ازمتن غیرقطعیه!!!!
وقتی x=y اومده یعنی نمیشه با پشته تشخیص داد . این زبان مستقل از متن نیست با این محدودیت .
x<>y هم مثل اینه که بخوای بررسی کنی که x=y هست یا نه که باز هم مستقل از متن نیست .
اما با محدودیت های x=yR و تعداد حروف x و y برابر نباشه مستقل از متن هست .
پس میشه گزینه ۱
یکی ازسوالایی که من امسال قطعی زدم همین بود چون این سوالو قبلاً خونده بودم (گزینه ۳) حتی پارسال به مدت یه روز تو سایتا گشتم تا ماشینشم پیدا کنم ولی آخر خودم ماشینشو کشیدم اگه بخواین npda هاش رو براتون میزارم فقط اینو بهتون بگم که ماشین ۲ بار به صورت غیرقطعی تشخیص میده.
سلام بر همگی
این سوال ۵۷ داره جالب می شه
بعضی از دوستان استدلال می کنن که x رو لامبدا می گیریم و شرط x!=y به ازای هر مقداری برای y برقراره.
حرف شما در مورد عبارتهای منظم، گرامرها و ماشین ها درسته، یعنی اگه در هر کدوم از این ابزارهای توصیف زبان یک راه برای تولید یک رشته پیدا بشه، اون رشته عضو زبان هست و پذیرفته می شه.
اما اینجا نحوه توصیف زبان فرق داره و باعث ایجاد ابهام شده. در واقع مشکل سر استفاده از سور وجودی و عمومیه.
مثالا یک رشته رو در نظر بگیرین. (aa)
یه تفسیر اینه که: رشته ای عضو زبان هست که حداقل یک x و y وجود داشته باشه که بتونیم توی رشته اختیار کنیم و به ازای اون شرط x!=y برقرار باشه. مثلا x=lambda می گیریم و y=aa پس رشته aa عضو زبان هست.
تفسیر دیگه اینه: رشته ای عضو زبان هست که به ازای تمام x و y های ممکن شرط برقرار باشه. یعنی برای aa چون می تونیم x=a y=a قرار بدیم و این مسئله باعث نقض شرط x!=y می شه، پس aa عضو زبان نیست.
به نظر من همونطور که گفتم تفسیر اول در مورد ابزارهایی مثل عبارات منظم و گرامرها و ... قابل انجامه، یعنی وجود یک راه برای بدست آوردن رشته کافیه. (در واقع تعریفشون و کاربردشون همینه)
ولی در این مورد چون یک بیان ریاضی از زبان رو داریم باید به ازای هر x و y ممکن، شرط درست باشه تا بتونیم رشته رو بپذیریم. بنابراین تفسیر دوم درسته.
منظورم اینه که یک عبارت ریاضی اگر درست باشه، همواره درسته. نمی شه توی شرایطی نادرست باشه. مثلا تو منطق و ریاضیات شما سه تابع داری : f(x)=x g(x)=x h(x)=2x
مطمئنا قبول دارید که f=g هست و g=h نیست. یعنی با اینکه مقدار g و h به ازای x=0 با هم برابر هست، اما g با h برابر نیست.
امیدوارم منظورم رو رسونده باشم.
سئوال ۵۵ من نزدم و تحلیل ام درست بود سر جلسه ۲ گزینه ۱ و ۳ جواب می شد
دلیلشم خیلی راحت چون ماشین پشته ای که داشتیم تعدادی فرد a می خواست و در انتها با اپسیلون می رفت به حالت پایانی ولی برای گرامر های ۱ و ۳ می توانیم مثال نقض آورد که ماشین بره تو حالت تله
خدا کنه حذف بشه چون کسی زده ۱ و کس زده ۳ داله بر فهمش نمیشه و اونیکه نزده هم داله بر بی دانشیش نمی شه
لطفا نظر بدهید
(۲۶ بهمن ۱۳۹۱ ۱۰:۳۵ ب.ظ)Mahdi .Tahmouresi نوشته شده توسط: سئوال ۵۵ من نزدم و تحلیل ام درست بود سر جلسه ۲ گزینه ۱ و ۳ جواب می شدسلام مهدی جان با عرض شرمندگی باید بگم با اونکه کلید مدرسان میگه گزینه ۲ درسته و من نمیدونم سر جلسه مخم فسفر نداشته که مثل حل کننده مدرسان فکر کردم ولی اینو باید بگم که جواب گزینه ۱ هستش به این دلیل که گزینه ۱ رشته های a,2a,4a,6a,... رو تولید میکنه که بجز یک a شامل رشته های فرد نمیشه !! گزینه ۲ a,3a,5a,... تولید میکنه که با ماشین مطابق هست- گزینه ۳ رشته های a,2a,3a,4a,5a,6a,... تولید میکنه و با وجود اینکه رشته های اضافی تولید میکنه رشته های ماشینم تولید میکنه-گزینه ۴ هم رشته های شامل گزینه ۲ رو تولید میکنه که درسته- حالا نتیجه: گزینه ۱ رشته های ماشین رو تولید نمی کنه ولی ۳ تولید میکنه هرچند رشته های اضافی هم تولید کنه با توجه به صورت سوال که معادل بودن نخواسته و فقط گفته آیا گرامر توانایی تولید زبان رو داره یا نه؟؟ پس جواب همون گزینه ۱ میتونه باشه!!! حالا ۱ سوال من از دوستان می پرسم سر جلسه من چم بوده؟؟؟ این سبک سنجیدن اونم توو اون تایم کم خیلی نامردیه اونم واسه منی که تنها مشکلم سر کم بودن زمان و استرسی که همین موضوع بهم وارد میکرد بود!!
دلیلشم خیلی راحت چون ماشین پشته ای که داشتیم تعدادی فرد a می خواست و در انتها با اپسیلون می رفت به حالت پایانی ولی برای گرامر های ۱ و ۳ می توانیم مثال نقض آورد که ماشین بره تو حالت تله
خدا کنه حذف بشه چون کسی زده ۱ و کس زده ۳ داله بر فهمش نمیشه و اونیکه نزده هم داله بر بی دانشیش نمی شه
لطفا نظر بدهید
(۲۴ بهمن ۱۳۹۱ ۱۲:۳۷ ب.ظ)rezareza2 نوشته شده توسط: بچه ها سوال ۵۵ رو چی زدید ؟
من هنوز فکر میکنم سوال ماشین تورینگ اشتباه باشه،وقتی ورودی رو بشکل x=11 و y=1 بدید ( درواقع رشته ورودی ۱۱۰۱) جوابی که در میاد ۱۱۱۱ میشه،این در هیچ کدوم از گزینه ها صدق نمیکنه !!
نظر دوستان چیه ؟
اگه منظورتون تست ۵۴ هستش باید بگم در حالتهایی که y فرد باشه گزینه یک درسته و در حالتهایی که y زوج باشه گزینه ۲ درسته گزینه های ۳ و ۴ کاملا غلطن . من که خودم ۲ رو زدم.میتونی امتحان کنی:دو حالت ۱۱۱۰۱۱۱ و۱۱۱۰۱۱ رو امتحان کن.
در هردو حالت گزینه ۱ در میاد
سلام علی جان
آقا کاش مانشت Voice داشت، از تحلیلت خوشم آمد ولی بازم سر حرفم هستم دلیل هم دارم برای رد تحلیلت نگاه کن شما گفتی که گزینه ۱ نمی تونه همه رشته های فرد a را تولید کنه من می گم می تونه دلیل هم داره خیلی ساده شما گرامر را باز نویسی کنید با این تغییر که بجای aB در قواعد خط ۱ و ۲ حرف M را به عنوان مثال قرار بده حاله از اونجا که ماشین پشته ای و همچنین برای اینکه گرامر مبهم نداشته باشیم می دونیم که باید از (Left Most Driviton) استفاده کنیم خوب پس تا M را از درخت اشتقاق به برگ نرسانیم نمی توانیم ادامه قاعده ۱ را دنبال کنیم پس می توان همه جملاتی که فرد a را دارند تولید کنیم و بعد از آن برای ترمینیت کردن مجبوریم از قاعده ای استفاده کنیم که انتهاش اپسیلون داره و بعد از آن اگر aa های قاعده ۱ول بیاد حالت dont care داره
البته باز این یک نظره بررسی کنید
(۲۳ بهمن ۱۳۹۱ ۱۲:۳۶ ق.ظ)ADELZX نوشته شده توسط:مهندس شما که میگی لوپا را حذف کن پس نتیجه میگیریم گزینه ۳ درسته یعنی bab,aba یک دفعه چک کن!(22 بهمن ۱۳۹۱ ۰۳:۲۲ ب.ظ)rezareza2 نوشته شده توسط:(22 بهمن ۱۳۹۱ ۰۱:۲۸ ب.ظ)ADELZX نوشته شده توسط:اما گزینه ۳ که aaa رو نمیتونه تولید کنه؟! یکبار دیگه چک کن دوست من.(22 بهمن ۱۳۹۱ ۰۱:۲۸ ق.ظ)rezareza2 نوشته شده توسط: سوال ۵۳ گزینه ۴ درسته.دوست عزیز چک کردیم ۵۵ همون گزینه ۱ درسته که سه تا a رو تولید نمیکنه. بقیه تولید میکنن. موفق باشی
اون لوپ ها که بی تاثیره، حذفشون کنید( البته فقط در این مثال بی تاثیره و قاعده کلی نیست ) می بینید که هم رشته ab و هم رشته ba رو در هر مسیر می تونید بیابید.
پس گزینه درست این سوال ۴ هست ،
اما این سوال ۵۴ بنظرم اشتباهه، شما x=11 و y=1 در نظر بگیر، پس ورودی ۱۱۰۱ هست حالا چک کن خروجی ۱۱۱ میشه.و تو هیچ کدوم از گزینه ها هم نیست!
سوال ۵۷ گزینه درست ۳ هست. اون حالت نامساوی رو براحتی میتونید با یک اوماتای پشته ای نامعین چک کنید.
اون سوال ۵۵ هم اشتباهه بنظرم و دلیلشم متاسفانه یک غلط تایپیه!
ببینید اتوماتای ما رشته aaa رو میپذیره.
همین برای رد گزینه کافیه .
خودتون چک کنید می بنید بیش از یک گزینه یعنی گزینه ۱ و گزینه ۳ این رشته رو نمی پذیره ...
دوست عزیز من تنها درسی که بلدم نظریه هست . این چیز پیش پا افتاده که میگی رو چک کردم ولی بازم ....
(۲۵ بهمن ۱۳۹۱ ۱۲:۱۰ ب.ظ)pooya نوشته شده توسط: ۵۷ گزینه ۳ می شه دکتر کارگهی کاملا گفته که چرا x=/y را می شه براش زبان مستقل از متن انم ازنوع غیر قطعی نوشتکاملا با گزینه ۳ موافقم.
سوال ۵۳و ۵۵ دو جواب صحیح دارن.مثلا در سوال ۵۳ به حالت پذیرش نگاه کنید .کپی این تست و این شکل در سال ۹۰ اومده بودمتاسفانه امسال شکل را اشتباه رسم کردن.با توجه به این شکل گزینه ۳ و ۴ هر دو صحیح هستن.
(۲۱ بهمن ۱۳۹۱ ۱۱:۴۵ ب.ظ)sarous نوشته شده توسط: سوال ۵۳ بدون شک پاسخش گزینه ۱ هست.گزینه ۲ و ۳ تابلوه که غلطه.این ماشین میتونه aba رو در حالت نهایی قرار بده در این حالت وقتی زیر رشته ab رو جستجو کنی وجود داره و در انتها یک a میمونه پس شامل ba نشد و برعکس.گزینه ۱ میگه ترکیبی از a و b ها که حتما شامل زیر رشته ab یا ba هست که اثبات کردم.
سوال ۵۴ گزینه ۱ میشه.سوال ساده ایه.
نظریه رو همین ۲ تا زدم ولی بجاش مدار منطقی رو کامل جواب دادم.
======
اولا که سنجش گزینه ی ۴ رو انتخاب کرده
ثانیا من ثابت کردم همه ی گزینه ها غلط هستن :
بچه ها اینو اعتراض کنید:
درس نظریه زبانها
مهندسی کامپیوتر ۹۲ ارشد:
--
سوال ۵۳ نظریه بر حسب دفترچه B
به نظرم مشکل داره:
-----
aabbba رو می گیره،تعداد a و b فرد هست پس ۲ هم غلطه.
همچنین رشته ی aabbba شامل abaوbab نیست پس ۳ هم غلطه.
baba رو نمی گیره پس ۴ هم غلطه.
--
گزینه ی ۱ هم نمیشه گفت کاملا درسته زیرا abb رو نمی گیره
----
بخش بحث اعتراض :
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
سوال ۵۷ x#y مستقل از متن نیست .حالا چرا ؟
به ازای هر زبان مستقل از متن یک اتوماتای پشته ای وجود دارد .
باید ابتدای x را با ابتدای y مطابقت دهیم که ببینیم مخالف هستند یا نه اگر مساوی برویم سراغ حرف بعدی که برای این کار باید اول آن حرف هایی را که از ابتدا (x) تا ابتدای y را وارد کرده ایم (پشته ) را از ماشین خارج کنیم تا به ابتدای رشته x برسیم و بعد تطابق دهیم که با این کار رشته x از دست می رود .
این دقیقا مانند X=Y است (برای هر دو باید ابتدای دو رشته با هم مقایسه شوند که با این کار بخشی از رشته X از بین میرود) حالا نمیدانم چرا این را طراح این مستقل ازمتن در نظر گرفته .
(۰۳ اسفند ۱۳۹۱ ۰۶:۳۳ ب.ظ)sadeghpc نوشته شده توسط: سوال ۵۷ x#y مستقل از متن نیست .حالا چرا ؟
به ازای هر زبان مستقل از متن یک اتوماتای پشته ای وجود دارد .
باید ابتدای x را با ابتدای y مطابقت دهیم که ببینیم مخالف هستند یا نه اگر مساوی برویم سراغ حرف بعدی که برای این کار باید اول آن حرف هایی را که از ابتدا (x) تا ابتدای y را وارد کرده ایم (پشته ) را از ماشین خارج کنیم تا به ابتدای رشته x برسیم و بعد تطابق دهیم که با این کار رشته x از دست می رود .
این دقیقا مانند X=Y است (برای هر دو باید ابتدای دو رشته با هم مقایسه شوند که با این کار بخشی از رشته X از بین میرود) حالا نمیدانم چرا این را طراح این مستقل ازمتن در نظر گرفته .
این دقیقا مثل x=y نیست چون اینجا هیچ محدودیت دیگری روی x و y نذاشته پس x و y هر چیزی می‌تونن باشن و نیازی به مقایسه اونها نیست
در واقع میشه y رو برابر [tex]\lambda[/tex] گرفت و در نتیجه X هر چیزی که باشه شرط [tex]x\neq y[/tex] برقرار خواهد بود
پس زبانمون همه چیز در [tex]\Sigma ^{*}[/tex] رو شامل میشه بجز [tex]\lambda[/tex] (که همچین تجزیه‌ای نداره)
یعنی زبانمون [tex]\Sigma ^{ }[/tex] هست که نه تنها مستقل از متنه که منظم هم هست
چرا میگین حالت x#y با x=y فرق میکنه؟
ببینید یک شرط در هر دو حالت داریم و اون شرط باید برقرار باشه یعنی در حالت اول حتما" باید x#y باشد و در حالت دوم حتما" باید x=y باشد . کجای صورت مساله گفته x#y میتواند باشد؟ که ما بگیم که خب از اونجاییکه هم میتونه باشه و هم نمیتونه باشه پس میشه سیگما ستاره .
حالا یه مثال میزنم :
فرض کنیم الفبا ۰ و ۱ باشه و x=1001 و y=1001 و به قول شما یهPDA وجود داشته باشه که رشته های xy که x#y باشه رو قبول میکنه.حالا شما با استفاده از یهPDA نشون بده که عبارت xy که داده شده توسط آن ماشین پذیرفته خواهد شد.