تو کتابای مختلف خواص بستاری مختلفی واسه زبانها ارائه شده که تو مواردی با هم تناقض دارند.یه جمع بندی اینجا میزارم اگه کسی اشکالی توش دید اصلاح کنه که واسه جمع بندی دچار اشتباه نشیم.
1-REG ,REC نسبت به تمام خواص بسته هستند.(اجتماع -اشتراک-الحاق-بستار ستاره-معکوس-متمم-همومورفیسم-تفریق-تقسیم)
استثنا:REG نسبت به اجتماع و اشتراک نامتناهی بسته نیست.
2-DCF فقط نسبت به مکمل بسته است.(جایی دیدم نسبت به معکوس هم بسته بود!)
3-RE نسبت به تمام خواص به جز مکمل و تفریق بسته است
4-CF نسبت به (اجتماع-معکوس-همومورفیسم-الحاق-بستار ستاره -اشتراک منظم-تفریق منظم-تقسیم منظم)
5-CS نسبت به (اجتماع-معکوس-همومورفیسم-الحاق-بستار ستاره -اشتراک)
6-LIN نسبت به (اجتماع-معکوس-همومورفیسم-الحاق منظم-اشتراک منظم)
زبانهای منظم نسبت به اشتراک نامتناهی بسته اند.
چیزی که من یاد گرفتم:
1- زبانهای منظم کلا نسبت به همه چیز بسته اند. (به جز اجتماع و اشتراک نامتناهی)
2- زبانهای مستقل از متن فقط نسبت به مکمل و تفریق و اشتراک بسته نیستند و برای سایر بسته اند.
3- زبانهای حساس به متن و بازگشتی نسبت به همه چیز بسته اند به جز همریختی
4- زبانهای بازگشتی شمارا فقط نسبت به مکمل و تفریق بسته نیستند.
5 تحت عمل اجتماع،همریختی ،اشتراک منظم و الحاق منظم بسته هستند.
زبانهای خطی نسبت به۳عملگر اشتراک،الحاق و مکمل بسته نیستند.
(22 بهمن 1390 11:49 ب.ظ)پشتکار نوشته شده توسط: [ -> ]۲- زبانهای مستقل از متن فقط نسبت به مکمل و تفریق و اشتراک بسته نیستند و برای سایر بسته اند.
۳- زبانهای حساس به متن و بازگشتی نسبت به همه چیز بسته اند.
مطمئنید؟
(22 بهمن 1390 11:49 ب.ظ)پشتکار نوشته شده توسط: [ -> ]چیزی که من یاد گرفتم:
۱- زبانهای منظم کلا نسبت به همه چیز بسته اند. (البته اگه یکی در مورد نامتناهیش توضیح بده ممنون می شم.)
۲- زبانهای مستقل از متن فقط نسبت به مکمل و تفریق و اشتراک بسته نیستند و برای سایر بسته اند.
۳- زبانهای حساس به متن و بازگشتی نسبت به همه چیز بسته اند.
۴- زبانهای بازگشتی شمارا فقط نسبت به مکمل و تفریق بسته نیستند.
۵-زبانهای خطی یکی زحمتشو بکشه
سلام دوست عزیز:
****کتاب پارسه ص174:
زبان های حساس به متن و بازگشتی نسبت به همریختی بسته نیستند!!!****
زبانهای خطی تحت عمل اجتماع،همریختی ،اشتراک منظم و
الحاق منظم بسته هستند.
زبانهای خطی نسبت به3عملگر اشتراک،الحاق و مکمل بسته نیستند.
میشه در مورد تفاضل هم بگید چه زبان نسبت به تفاضل بسته هست و چه زبانی نیست.
تا اونجایی که من می دونم زبانهای مستقل از متن و بازگشتی شمارا نسبت به تفاضل بسته نیستند.
(23 بهمن 1390 11:14 ق.ظ)NoOne نوشته شده توسط: [ -> ] (22 بهمن 1390 11:49 ب.ظ)پشتکار نوشته شده توسط: [ -> ]۲- زبانهای مستقل از متن فقط نسبت به مکمل و تفریق و اشتراک بسته نیستند و برای سایر بسته اند.
۳- زبانهای حساس به متن و بازگشتی نسبت به همه چیز بسته اند.
مطمئنید؟
من از منبعی که خوندم همریختی رو در نظر نگرفته بود.
پس جمع بندی میتونه اینطوری باشه که فقط زبانهای مستقل از متن قطعی و حساس به متن و بازگشتی نسبت به همریختی بسته نیستند.
هر زبانی که نسبت به مکمل و اشتراک بسته باشد، نسبت به تفاضل هم بسته هست
زبان های منظم نسبت به تفاضل بسته هست
خانواده های زبان های مستقل از متن تحت اشتراک و مکمل گیری بسته نیست، پس تحت تفاضل بسته نیست اما تحت تفاضل منظم بسته هست یعنی A-B
که A: مستقل از متن باشه و B منظم، حاصل مستقل از متن هست
خانواده زبان های مستقل از متن نسبت به همریختی بسته هستند.