سلام
مجموعه تمام عبارات منظم روی { a ,b }
۱-مجموعه غیر قابل شمارش است .
۲-یک زبان منظم است
۳-یک زبان مستقل از متن است.
۴-ذاتا مبهم است
آیا گزینه ۱ می شه.
این نظر شخصی منه دوستان میتونن اصلاح کنن
گزینه ۲ درسته ،منظم هستش
گزینه اول غلطه چون مجموعه عبارات منظم متناهی است و قابل شمارش
نکته :مجموعه متناهی همواره منظم است .
گزینه ۴ غلظه چون عبارات منظم ذاتا مبهم نیستند .
گزینه سوم به نظر من بعد گزینه ۲ درسته البته زبانهای منظم زیر مجموعه زبانهای مستقل از متن هستش
اگه کامل نیست بگید تا بازم روش بحث کنم
(۲۰ اردیبهشت ۱۳۹۱ ۰۷:۰۹ ب.ظ)yaser_ilam_com نوشته شده توسط: گزینه اول غلطه چون مجموعه عبارات منظم متناهی است و قابل شمارشالبته اگه متناهی بود حتما منظم بود ولی متناهی نیست.
نکته :مجموعه متناهی همواره منظم است .
مجموعه ی عبارات منظم شامل a و b متناهی نیست چون ما در مورد مجموعه ی عبارات منظم هر ترکیبی از a و b رو میتونیم داشته باشیم. مجموعه نا متناهی است و شمارا .
پس دقیقا نمیتونیم بگیم که منظم هستند. یعنی من دلیلی واسه منظم بودنش پیدا نکردم.
البته بله متناهی نیست اشتباه نوشتم اکثر زبان های مورد علاقه نامتناهی هست اما همون طور گفتید قابل شمارش است و گزینه ۱ غلظ
گزینه ۴ هم حتما غلظه حالا بین ۲ و ۳ کدام درسته؟ فکر نمی کنید مجموعه عبارات منظم ،منظم باشه؟
ببینید قضیه ۳-۲ کتاب لینز ویرایش سوم :
اگز دو عبارت [tex]r1 ,r2[/tex] منظم باشد آنگاه :
[tex]L( r )=L(r1 r2)=L(r1)\cup L(r2)[/tex]
یعنی اجتماع دو عبارت منظم منظم هست این میتونه استدلال من باشه اما گزینه ۲ درستتره نسبت به گزینه ۳
(۲۰ اردیبهشت ۱۳۹۱ ۰۸:۱۵ ب.ظ)yaser_ilam_com نوشته شده توسط: ببینید قضیه ۳-۲ کتاب لینز ویرایش سوم :
اگز دو عبارت [tex]r1 ,r2[/tex] منظم باشد آنگاه :
[tex]L( r )=L(r1 r2)=L(r1)\cup L(r2)[/tex]
یعنی اجتماع دو عبارت منظم منظم هست این میتونه استدلال من باشه اما گزینه ۲ درستتره نسبت به گزینه ۳
کاملا دلیلتون درسته.
[tex]\sum ^{*}[/tex] همیشه یک زبان منظم هست حالا این [tex]\sum[/tex] میتونه شامل هر تعداد الفبا باشه . که اینجا a و b هست
با نظر شما موافقم گزینه ی ۲ و ۳ هر دو میتونن درست باشن اما خب جواب درست تر همون گزینه ی ۲ هست.
اما اگه زبانمون اجتماع تعداد نامتناهی زبان منظم باشه چی؟؟
.... a *b a*b a .آون وقت که منظم نمی شه؟
ببخش مثالت رو درست نفهمیدم اما ...
[tex]r1=a^{*} , r2=b^{*}[/tex] حال هر کدوم منظم هستند حالا اجتماع اینها هم منظمه دیگه یعنی
[tex]r=r1 r2=a^{*} b^{*}[/tex]
این زبان حتما منظمه .
(۲۰ اردیبهشت ۱۳۹۱ ۰۹:۰۶ ب.ظ)BJS نوشته شده توسط: اما اگه زبانمون اجتماع تعداد نامتناهی زبان منظم باشه چی؟؟متناهی بودن یک مجموعه دلیلی برای منظم بودن هست اما با نامتناهی بودن نا منظم بودن اثبات نمیشه .
.... a *b a*b a .آون وقت که منظم نمی شه؟
ما زبان های زیادی داریم که نا متناهی هستند اما منظمن مثلا عبارت :[tex]a^{*}b^{*}[/tex]
مثلا این عبارتی که مثال زدم را میتونیم به صورت مجموعه تعریف کنیم و بگیم مجموعه ی ترکیب های a و b که اول a بیاد و بعدش b حالا این مجموعه میشه نامتناهی اما همون طور که میبینی زبانی که براش مینویسیم یک زبان منظم هست.
منظورم اینه که مثلا اگر A,B دو عبارت منظم باشد آنگاه\sum ^{}\infty (A^{n}UB^{n})
منظم نیستند....خانواده زبان های منطم تحت اجتماع نامتناهی بسته نیستند....
[tex]\sum ^{}\infty {A^{^{n}}UB^{n}}[/tex]
مثالی هست که بالا زدم
مثال نقض برای حرف شما :
[tex]\sum ^{*}[/tex] یک مجموعه ایی از الفبای سیگما میباشد اما منظم است. و در این مجموعه عبارات نامتناهی وجود دارن
و همین طور مثال قبلی که برای شما زدم باز هم حرف شما رو نقض میکنه.
سلام
پاسخ صحیح گزینه ۳ هست .
زبان های منظم تحت اجتماع نا متناهی بسته نیست.
(۲۱ اردیبهشت ۱۳۹۱ ۰۸:۰۹ ق.ظ)Mojtaba نوشته شده توسط: سلام
پاسخ صحیح گزینه ۳ هست .
زبان های منظم تحت اجتماع نا متناهی بسته نیست.
بسیار ممنون از جوابتون نمی دونم چرا رو این نکته دقت نکردم دو نکته بسیار مهم و جالب :
نکته ۱ : زبانهای منظم تحت اشتراک نامتناهی بسته است ،تمرین۱۷ ص ۱۱۸ لینز ویرایش سوم
نکته ۲ : زبانهای منظم تحت اجتماع نامتناهی بسته نیست ،تمرین۱۵ ص ۱۱۸ لینز ویرایش سوم
با این استدلال میشه گزینه ۳ ،مستقل از متن
بازم ممنون از راهنماییتون