تالار گفتمان مانشت
گرامر مستقل از متن - نسخه‌ی قابل چاپ

گرامر مستقل از متن - Sanazzz - 12 دى ۱۳۹۷ ۰۲:۳۰ ق.ظ

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


[تصویر:  465020_qh0v_p_20190102_003924_vhdr_on_1.jpg]

[تصویر:  465020_4ah0_p_20190102_003938_vhdr_on_1.jpg]

[تصویر:  465020_7sr8_p_20190102_004542_vhdr_on_1.jpg]

[تصویر:  465020_1646_p_20190102_004550_vhdr_on_1.jpg]

خواهشا کمکم کنین
با تشکرات بسیار بسیار ویژه

من خیلی رو سوالا فکر کردم
یه چیزی به ذهنم رسید میگم اگر بتونیم از یک زبان یه رشته ای رو انتخاب کنیم که بشه اون رشته رو با ماشین پشته ای انجام بدیم و در نهایت پشته خالی باش میتونیم بگیم زبانمون مستقل از متن؟
مثلا الان برای سوال ۷ من این رشته هایی که بالاش نوشتمو تونستم با ماشین پشته ای به جواب برسونم
ولی برای سوال ۹ که به غیر از a و b حرف cهم وجود داره نمیدونم اصلا ماشین پشته ای چطوری کار میکنه؟؟میشه کمک کنین لطفا
[تصویر:  465020_nfa8_p_20190102_182908_vhdr_on_1.jpg]

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

RE: گرامر مستقل از متن - Saman - 12 دى ۱۳۹۷ ۰۸:۲۱ ب.ظ

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

RE: گرامر مستقل از متن - Sanazzz - 12 دى ۱۳۹۷ ۰۸:۴۲ ب.ظ

(۱۲ دى ۱۳۹۷ ۰۸:۲۱ ب.ظ)Saman نوشته شده توسط:  سلام
پیام درخواست کمکتون رو دیدم
اما باور کنید نظریه زبان بلد نیستمSmile
شرمنده
باش
بازم ممنون جوابمو دادین
خیلی ممنون
تشکر

RE: گرامر مستقل از متن - ph0en1x - 12 دى ۱۳۹۷ ۰۹:۱۴ ب.ظ

خودتون درست به نتیجه رسیدید.
من نظریه رو هنوز نرسیدم به بخش مستقل از متن ولی تا جایی که از قبل یادمه با پشته پردازش میکردیم (فقط قطعی و غیرقطعیش یادم نیست)!
برای سوال نه برای زبان L1 با استفاده از پشته نمیشه رشته رو پردازش کرد (به شرط دقت کنید، گفته n باید بزرگتر مساوی m باشه که نمیتونیم با پشته این کارو بکنیم.
زبان L2 میشه همون an bn cm که اون رو میشه با پشته پردازش کرد، هرچی a دیدیم وارد پشته می کنیم، هرچی b دیدیم یه a پاپ می کنیم و هرچی c دیدیم ignore می کنیم. (چون i و j و k به هم وابسته نیستند و تنها شرطی که باید رعایت کنیم اینه که بزرگتر یا مساوی صفر باشن)
زبان L3 هم که با توجه به اینکه با L1 جمع شده، میشه زبان an bm cn که شرطش اینه که n و m بزرگتر از صفر باشن. که اینم میتونیم هرچی a دیدیم وارد پشته کنیم، هرچی b دیدیم ignore کنیم و هرچی c دیدیم یه a از پشته پاپ کنیم. (اگه شرط دوتا زبان رو روی هم در نظر بگیریم، قسمت اول زبان L3 میگه j باید بزرگتر از i باشه و قسمت دوم L3 که همون L1 میشه، میگه که n باید بزرگتر مساوی m باشه، این دوتا شرط رو باهم ترکیب کنیم، این شرط ایجاد میشه که m و n باید بزرگتر مساوی صفر باشن).
یه مقداری عجله‌ای نوشتم اگه متوجه توضیحاتم نشدید بگید روی کاغذ بنویسم بفرستم براتون.

RE: گرامر مستقل از متن - Sanazzz - 12 دى ۱۳۹۷ ۰۹:۵۹ ب.ظ

(۱۲ دى ۱۳۹۷ ۰۹:۱۴ ب.ظ)ph0en1x نوشته شده توسط:  خودتون درست به نتیجه رسیدید.
من نظریه رو هنوز نرسیدم به بخش مستقل از متن ولی تا جایی که از قبل یادمه با پشته پردازش میکردیم (فقط قطعی و غیرقطعیش یادم نیست)!
برای سوال نه برای زبان L1 با استفاده از پشته نمیشه رشته رو پردازش کرد (به شرط دقت کنید، گفته n باید بزرگتر مساوی m باشه که نمیتونیم با پشته این کارو بکنیم.
زبان L2 میشه همون an bn cm که اون رو میشه با پشته پردازش کرد، هرچی a دیدیم وارد پشته می کنیم، هرچی b دیدیم یه a پاپ می کنیم و هرچی c دیدیم ignore می کنیم. (چون i و j و k به هم وابسته نیستند و تنها شرطی که باید رعایت کنیم اینه که بزرگتر یا مساوی صفر باشن)
زبان L3 هم که با توجه به اینکه با L1 جمع شده، میشه زبان an bm cn که شرطش اینه که n و m بزرگتر از صفر باشن. که اینم میتونیم هرچی a دیدیم وارد پشته کنیم، هرچی b دیدیم ignore کنیم و هرچی c دیدیم یه a از پشته پاپ کنیم. (اگه شرط دوتا زبان رو روی هم در نظر بگیریم، قسمت اول زبان L3 میگه j باید بزرگتر از i باشه و قسمت دوم L3 که همون L1 میشه، میگه که n باید بزرگتر مساوی m باشه، این دوتا شرط رو باهم ترکیب کنیم، این شرط ایجاد میشه که m و n باید بزرگتر مساوی صفر باشن).
یه مقداری عجله‌ای نوشتم اگه متوجه توضیحاتم نشدید بگید روی کاغذ بنویسم بفرستم براتون.
نهایت تشکر
واقعا ممنونم
خدا خیرتون بده
انشالله کنکور هرچی میخواین بیارید
روم نمیشد ازتون بپرسم
خیلی ممنون واقعا تشکرات ویژژژژژژه