تالار گفتمان مانشت

سلام

من هنوزم نمیتونم زبان های مستقل از متن رو خوب تشخیص بدم.
لطفاً رو این سه تا زبان توضیح بدید.



[attachment=17790]

یک فرمول داره که بچه ها فک کنم زیاد ازش استفاده کنن ولی من چون از فرمول یاد گرفتن خوشم نمیاد اصلا از اون حل نمیکنم .

بنظرم بهترین راه فک کردن به ساخت ماشین پشته ای برای زبانه (نه اینکه ماشین و طراحی کنین فقط به ممکن بودن طراحیش فک کنید البته اینکه ماشین می تواند غیر قطعی هم باشه خیلی مهمه باید حواستون جم باشه)

مثلا زبان اول :
ماشین اگه اول b ببینه دیگه فقط b می تونه بیاد.
اما اگه اول a ببینه باید تعدادشون و تو پشته ذخیره کنه حالا از اینجا به بعد باید از عدم قطعیت کمک بگیریم یعنی با توجه به اینکه b وسط می تواند نیاید، باید به صورت غیر قطعی از یکجایی شروع به match کردن a های ورودی کنیم نه ذخیره، ولی اگه b دیدیم دیگه می تونیم قطعی تصمیم بگیریم.

زبان دوم و میشه بصورت قطعی پذیرفت من خودم یکم روش فک کردم تا مطمعن شدم زود نتونستم قطعی بودنشو تشخیص بدم، اول فک کردم غیر قطعیه.
داستانشم اینه که با دیدن b در ابتدا دیگه فقط میتونیم b ببینیم ولی اگه a دیدیم تعدادشو ذخیره می کنیم حالا اگه b دیدیدیم (شاید اصلا نبینیم که رشته در این حالت قبول است) شروع به match کردن می کنیم در این مرحله حالات زیر ممکنه رخ بدن ولی همشون قطعین :
- b ها match نمیشن و رشته تمام می شود : در این حالت رشته قبول است
- اگه قبل از اینکه همه b ها match بشن a ببینیم : قبول نیست
- اگه بعد از match شدن ، a ببینیم دیگه کافیه فقط ترتیب a و b های ادامه درست باشه .
- اگه b ها بیشتر از a ها بودن دیگه در ادامه فقط می تونه b باشه.

شاید بصورت تایپی نشه حق مطلب و ادا کرد ولی من اینطوری عمل میکنم.

سومی هم شبیه همینا تحلیل میشه کرد.
من فک کنم قطعی یا غیر قطعی بودن اینا مد نظر بوده چون مستقل از متن بودنشون واسه بچه ها راحته (با همون فرموله)

وای چه سخته سوالش...هول کردم...منم نمیفهمم

(30 دى 1393 02:36 ق.ظ)ریحان نوشته شده توسط: [ -> ]وای چه سخته سوالش...هول کردم...منم نمیفهمم

قطعی یا غیر قطعی بودنش به نظرم یک مقدار تمرکز بیشتری نسبت به سوالای معمول میخواد.

(30 دى 1393 03:19 ق.ظ)moloodi نوشته شده توسط: [ -> ]

(30 دى 1393 02:36 ق.ظ)ریحان نوشته شده توسط: [ -> ]وای چه سخته سوالش...هول کردم...منم نمیفهمم

به نظر من کاملا حق دارید سطح سوال از حد این آزمون های بدرد نخوره پارسه که ما می دیم بالاتره.

واسه تشخیص مستقل از متن بودن کافیه چک کنید که توان ها به فرم پرانتزی هستند یا نه و این که یه توان دو تا مقایسه نداشته باشه
مثلا زبان [tex]a^nb^ma^nb^m[/tex] اگه n رو پرانتز و m رو آکولاد فرض کنیم فرم زبانش این شکلیه {(}) که به فرم پرانتزی صحیح نیست
امام مثلا زبان اولی که تو عکس این تاپیک گذاشتن چون q,s فقط یه بار ظاهر شدن که مقایسه نمیشن و فقط p هست که مقایسه می شه و با در نظر گرفتن P به عنوان پرانتز زبانش می شه () که فرم صحیحه همه ی زبان های این عکس تاپیک به فرم صحیح پرانتزی هستن

یا مثلا تو بعضی زبان ها باید چک کنیم که هر عدد فقط یه بار مقایسه بشه مثلا زبان [tex]a^nb^ma^nb^{m n}[/tex] چون عدد n یه بار یا a های بخش دوم مقایسه شده یه بار با b های بخش دوم پس مستقل از متن نیست اما تمام زبان هایی که تو عکس این تاپیک گذاشتن همه ی اعداد فقط یه مقایسه می شن

پس نتیجه می گیریم همشون مستقل از متن هستند


اما برای تشخخیص قطعی بودن
باید هر بار چک کنید که p یا q یا s یا r اگه صفر بشن چی می شه
آیا ما از قطعیت در میایم یا نه
که دوستمون کامل توضیح دادن

دوستان چرا زبانی که در رشته ی w تعداد رشته های a مخالفb است مستقل از متن قطعیه؟ چطوری میشه توی پشته؟
خب ما که نمیدونیم اول a میاد یا b که ببینیم برای اومدن a علامت در پشته بذاریم یا برداریم؟ یا همینظورم واسه b؟ که بعد اگه بفهمیم a ها بیشترن یا b ها...

(11 بهمن 1393 07:34 ب.ظ)ریحان نوشته شده توسط: [ -> ]دوستان چرا زبانی که در رشته ی w تعداد رشته های a مخالفb است مستقل از متن قطعیه؟ چطوری میشه توی پشته؟
خب ما که نمیدونیم اول a میاد یا b که ببینیم برای اومدن a علامت در پشته بذاریم یا برداریم؟ یا همینظورم واسه b؟ که بعد اگه بفهمیم a ها بیشترن یا b ها...

می تونیم از یکسری نماد دیگه استفاده کنیم که نشان دهنده اون حالات باشن.
مثلا :
a دیدیم و پشته خالی بود A بذار.
b دیدیم و پشته خالی بود B بذار.
a دیدی و A روی پشته بود یک A دیگه روش بذار بشه AA.
b دیدی و روی پشته B بود یک B دیگه روش بذار بشه BB.
a دیدی و روی پشته B بود اونو از تاپ پشته حذف کن.
b دیدی و تاپ پشته A بود اونو از تاپ پشته حذف کن.

پس چرا کتاب جبل عاملی گفته این غیر قطعیه؟ وای خدا...چیکار کنم؟ پسww^r هم میشه قطعی که...

(12 بهمن 1393 01:03 ق.ظ)ریحان نوشته شده توسط: [ -> ]پسww^r هم میشه قطعی که...

نه دیگه . واسه زبان ww^r چون نمیدونیم وسط کجاس بصورت قطعی نمی تونیم تصمیم بگیریم باید از یکجایی همینطوری شانسی بگیم اینجا وسطه بعد بریم ببینم درست بوده یا نه.

وای کاملا حق با شماست.الان رفته بودم سراغ لینز دیدم گفته غیر قطعیه بعد روش قطعیشو گفته...اون وقت جبل عاملی فقظ گفته غیرقطعیه...الان کلا چن روز به کنکور دریچه ای جدید به روم باز شد.خخخخ
چه کاری شد..موندم چندتا اشتباه دیگه داشتم که این روشو نمیدونستم