تو کتاب پارسه گفته زبانهای منظم تحت "عمل اشتراک نامتناهی" بسته اند و تحت "عمل اجتماع نامتناهی" بسته نیستند . منظور از این دو عمل چیه؟
(۱۸ مهر ۱۳۹۱ ۰۲:۵۰ ب.ظ)irisadaf نوشته شده توسط: تو کتاب پارسه گفته زبانهای منظم تحت "عمل اشتراک نامتناهی" بسته اند و تحت "عمل اجتماع نامتناهی" بسته نیستند . منظور از این دو عمل چیه؟
یعنی اجتماع (یا اشتراک) تعداد نامتناهی رشته از زبان با طولهای مختلف
البته دکتر کارگهی تو حل تمرین مثال نقض آورده که تحت اشتراک هم بسته نیست (ص ۵۹ جزوه هاتف) !!!!!
منم با صحبت های دوستمون موافقم. اجتماع یا اشتراک تعداد نامتناهی زبان منظم لزوماً منظم نیست.
[tex]L_1\cap L_2\cap ...\cap L_n\cap ...=\overline{\overline{L_1}\cup \overline{L_2}\cup ...\cup \overline{L_n}\cup ...}[/tex]
با فرض منظم بودن همه زبانها نتیجه میگیریم مکملشون هم منظمه. پس اگه قرار باشه اشتراک های نامتناهی سمت چپ منظم باشن پس اجتماع های سمت راست هم منظمن (چون مکملش منظمه). فکر کنم به اندازه کافی مثال برای اثبات منظم نبودن اجتماع ها باشه. پس اشتراکشون هم لزوماً منظم نیست.
اجتماع نامتناهی یعنی تعداد نامتناهی تا زبان را با هم اجتماع بگیریم
(فرض خلف) اگر اجتماع نامتناهی زبان های منظم ، منظم باشد آن وقت همه ی زبان ها منظم هستند (که این تناقض است)
چظور از فرض خلف به این تناقض رسیدیم:
هر زبانی را که در نظر بگیرید از یه سری رشته ها تشکیل شده حالا ما بیاییم هر کدام از این رشته ها را یک زبان در نظر بگیریم. مثلا برای زبان [tex]a^nb^n[/tex] را هر کدام از رشته هایش را یک زبان در نظر بگیریم. واضحه که اجتماع تک تک این رشته ها با هم خود زبان رامی سازد:
[tex]\{a^nb^n\}=\{\lambda\}\cup\{ab\}\cup\{aabb\}\cup\{aaabbb\}\cup....[/tex]
و واضحه که هر کدام از زبان های تک عضوی یک زبان منظم هستند (چون متناهی اند) حال ما در سمت راست آمده ایم نامتناهی تا زبان منظم را اجتماع گرفته ایم اگر اجتماع نامتناهی تا زبان منظم ، منظم باشد پس زبان سمت چپ نیز منظم است(تناقض)