دانشجو-ایا زبان مستقل از متن قطعی تحت عمل اجتماع بسته است؟
استاد:خیر
دانشجو-چرا؟
استاد-چون میتونم مثال بیارم که دو زبان مستقل از متن قطعی هست ولی اجتماعشون قطعی نیست
دانشجو-عجب مگه میشه به ما چیزی دیگه گفتید!
استاد-کی گفته من که نگفتم
دانشجو-استاد من میفتم؟
استاد نه فرزندم
دانشجو :میخام نکته شو بهم یاد بدین
استاد : نمیخایی فکر کنی؟
دانشجو: نه هنگم!
استاد : من بهت کمک میکنم فقط به سوالاتم جواب بده
دانشجو: ممون استاد گلم
استاد:زبان L , K چه نوع زبانی هستند؟
$L=\left \{ a^{n}b^{n} |n >=1 \right \} k=\left \{ a^{n}b^{2n} |n >=1 \right \}$
دانشجو: استاد این که راحته میشه هم L , هم K مستقل از متن قطعی ولی این چه ربطی به سوال من داشت
استاد: عجله نکن سوال دوم ج بده اجتماع دو زبان L و K چی میشه؟
دانشجو میشه مستقل از متن قطعی
استاد :اصلن میدونی قطعی به چه زبانهایی میگن؟
دانشجو: استاد من گیج شدم راستش قطعی نمیدونم چیه
استاد : این زبانها مستقل از متن چون با یک پشته قابل پیاده سازی هست اینو مشکل داری؟
دانشجو: چجوری؟
استاد: تعداد a رو میریزی تو پشته بعد به تعدا b از پشته پاپ میکنه
به عبارت دیگه تعداد b رو از رو تعداد a بدست میاریم
دانشجو:استاد خیلی راحته ادامه بدین
استاد:حالا مستقل از متن ها یا قطعی هست یا غیر قطعی
تو زبان L بعد از پوش کردن تعداد a درپشته فقط یک راه داریم و اون اینه که به تعداد b از پشته پاپ کنیم پس میشه قطعی
دانشجو: فهمیدم پس K هم میشه قطعی
استاد :بله حالا اجتماع دو زبان میشه چی؟
دانشجو:
$L\cup k =\left \{ a^{n}b^{n} |n >=1 \right \} \cup \left \{ a^{n}b^{2n} |n >=1 \right \}$
استاد :درسته حالا از رو اجتماع بگو قطعی هست یا نه؟
دانشجو: فهمیدم میشه غیر قطعی
چون بعد از پوش کردن n تا a هم میتونیم b به توان n تولید کنیم و هم میتونیم b به توان ۲n پس ماشین میوفته سر دوراهی و میشه غیر قطعی
استاد: پس نتیجه کلی چی میشه؟
دانشجو: میتونم از رو این مثال بگم زبانهای مستق از متن قطعی تحت اجتماع بسته نیستند
استاد : دقیقن
دانشجو: استاد ممنون
استاد : حالا اینو ج بده ایا زبانهای مستقل از متن تحت معکوس بسته است؟
دانشجو: استاد این که راحته با همون مثال میشه ثابت کرد که بسته نیستند
استاد: نمیشه
دانشجو: استاد من تو زبان L یک c الحاث میکنم ابتدای زبان ایا قبول دارین که اشتراک دو زبان میشه قطعی
$L=\left \{ ca^{n}b^{n} |n >=1 \right \} k=\left \{ a^{n}b^{2n} |n >=1 \right \}$
استاد : خب این چه جوری میشه قطعی؟
دانشجو:استاد چون بعضی رشته های زبان با حرف c شروع میشن دیگه گرامر در سر دوراهی نیست و یا رسته های زبان با c شروع میشن یا نمیشن
به عبارت دیگر اگر ابتدای رشته C اومد بعدش به تعداد a پوش میکنیم و به تعداد b پاپ میکنیم و فرقش با مثال قبلی همینه که تو قبلی بعد از پوش a تو پشته دو راه داشتیم پاپ به اندازه b به توان n یا b به توان ۲nپس اون قطعی نبود ولی این مثال قطعی هست
استاد : بله درسته خب حالا بعدش چی؟
دانشجو:خب حالا اگه معکوس کنیم زبان شبیه مثال خودتون میشه غیر قطعی
استاد :افرین
دانشجو:پس نتیجه کلی چی میشه؟
استاد: زبانهای مستقل از متن قطعی تحت معکوس بسته نیست
دانشجو:درسته استاد
استاد: افرین خوشم اومد بچه زرنگی هستی حالا یه سوال دیگه ایا زبانهای مستقل از متن قطعی تحت همریختی بسته اند؟
دانشجو:استاد یکم فکر کنم ...
فهمیدم استاد اینو ببینید
$O =\left \{ a^{n}b^{n} |n >=1 \right \} \cup \left \{ c^{n}b^{2n} |n >=1 \right \}$
قبول دارید این قطعی هست؟
استاد: بله
دانشجو من تابع زیر رو تعریف میکنم
$h(a)=a, h(b)=b , h©=a$
خب از تابع هموموفیسم خودم استفاده میکنم و نشان میدم زبان با این همومورفیسم خاص از قطعیت میفته
$O =\left \{ a^{n}b^{n} |n >=1 \right \} \cup \left \{ a^{n}b^{2n} |n >=1 \right \}$
اینم تو درس ثابت کردیم قطعی نیست
استاد: پس نتیجه کلی؟
دانشجو : که زبانهای مستقل از متن قطعی تحت همومورفیسم بسته نیستند
استاد: افرین درسته
دانشجو: استاد این ها چقدر شیرین هستند
استاد : افرین همینطوره فقط کافیه فکرت رو بکاربگیری
دانشجو :استاد من بازم مزاحم میشم امری نیست؟
استاد:نه فقط تمرین کن و مسله زیاد حل کن
دانشجو:خدانگهدار
استاد:خدا نگهدار
پس نتایج خلاصه درس واسه کنکوری ها که وقت نمیکنن متن رو بخونن!
۱-زبانهای مستقل از متن قطعی تحت اجتماع بسته نیستند
۲-زبانهای مستقل از متن قطعی تحت معکوس بسته نیستند
۳-زبانهای مستقل از متن قطعی تحت همومورفیسم بسته نیستند

(۲۰ دى ۱۳۹۱ ۱۱:۱۳ ق.ظ)ahmadnouri نوشته شده توسط:  دوستان من ۲ تا سوال دارم
۱- زبان های مستقل از متن قطعی تحت چه عملیاتی بسته اند؟
۲-اگر برای حذف قوانین بی فایده ابتدا متغیر هایی را که از شروع قابل دسترسی نیستند بعد انهایی را که به حالت نهایی نمی رسند
ایا این ترتیب حذف درست است؟ یا باید ترتیب حذف رو عوض کرد؟

سوال اول:
زبان مستقل از متن تحت اشتراک و مکمل گیری بسته نیست، در نتیجه زبان مستقل از متن قطعی هم تحت این دو عمل بسته نیست
زبان مستقل از متن تحت اجتماع و همریختی، بسته هست، ولی مستقل از متن قطعی تحت این دو عمل بسته نیست، چون ممکن است به مستقل از متن غیر قطعی تبیدل شود زبان.
مستقل از متن قطعی نسبت به الحاق و بستار ستاره ای بسته نیستند.
سوال دوم:
ترتیب حذف:
۱/ به پایانی منجر نمیشن
۲/ از شروع به آنها راهی نیست
ترتیب حذف مهم است، اگه ترتیب حفظ نشه، همه قوانین بی فایده حذف نمیشن
مثال:
[/align]S->aA|aC
C->c|lambda
A->aA

حذف متغیر هایی که از شورع به آنها راهی نیست: چیزی حذف نمیشه
حذف متغیرهایی که به پایانی منجر نمیشن:
با اینکه بی فایده هست، در گرامر باقیمانده