سلام
این سوال از کتاب پارسه هست:
با فرض [tex]L_2=\{a^n\: b^l\: \mid\: n,l\: \ge\: 0\}[/tex] و [tex]L_1=\{a^n\: b^l\: \mid\: n\: \ne l\}[/tex] کدام گزینه صحیح است؟
۱) زبان [tex]L^-_1[/tex] (متمم زبان L1) یک زبان منظم نمیباشد.
۲) زبان [tex]L_1\cup\: L_2[/tex] یک زبان منظم نمیباشد.
۳) زبان [tex]L^-_1\cap\: L_2[/tex] یک زبان منظم میباشد.
۴) زبان [tex]L_1\cap\: L_2[/tex] یک زبان منظم میباشد.
جواب کتاب: گزینه ۱
زبان L1 مستقل از متن هست و زبان L2 منظم، درسته؟
گزینه اول که درسته چون زبان های مستقل از متن تحت مکمل گیری بسته نیستن.
زبان های مستقل از متن تحت اجتماع بسته اند، زبان های منظم هم تحت اجتماع متناهی بسته اند.
اجتماع یک زبان مستقل از متن و یک زبان منظم مستقل از متن هست یا منظم؟
زبان L2 چرا منظمه؟!
زبان هایی داریم که هم مستقل از متن قطعی باشن هم غیر قطعی؟!
برای هر زبان مستقل از متن قطعی میشه گرامر غیرقطعی نوشت؟
لطفاً توضیح بدید.
سلام.
اجتماع و اشتراک منظم و مستقل از متن در حالت کلی مستقل از متنه. ولی میتونه منظم هم باشه. اگه زبان منظم زیرمجموعه زبان مستقل از متن باشه اشتراک دو زبان منظمه و اگه زبان مستقل از متن زیرمجموعه زبان منظم باشه اجتماعشون منظمه. البته این دو شرط هم شرط کافی هستن.
L2 که منظمه. میشه [tex]a^*b^*[/tex].
زبانهای مستقل از متن قطعی زیرمجموعه ای از زبانهای مستقل از متن غیرقطعین. همونطور که زبانهای منظم زیرمجموعه زبانهای مستقل از متن قطعین.
(۲۹ دى ۱۳۹۳ ۰۴:۵۱ ب.ظ)Jooybari نوشته شده توسط: سلام.
اجتماع و اشتراک منظم و مستقل از متن در حالت کلی مستقل از متنه. ولی میتونه منظم هم باشه. اگه زبان منظم زیرمجموعه زبان مستقل از متن باشه اشتراک دو زبان منظمه و اگه زبان مستقل از متن زیرمجموعه زبان منظم باشه اجتماعشون منظمه. البته این دو شرط هم شرط کافی هستن.
L2 که منظمه. میشه [tex]a^*b^*[/tex].
زبانهای مستقل از متن قطعی زیرمجموعه ای از زبانهای مستقل از متن غیرقطعین. همونطور که زبانهای منظم زیرمجموعه زبانهای مستقل از متن قطعین.
خانواده زبان های مستقل از متن قطعی و غیرقطعی طبق تعریف، دو مجموعه کاملاً disjoint هستند.
خانواده زبان های مستقل از متن قطعی زیرمجموعه زبان های مستقل از متن هست.
البته برای هر زبان مستقل از متن قطعی میشه گرامر غیرقطعی نوشت.
(۲۹ دى ۱۳۹۳ ۰۴:۵۱ ب.ظ)Jooybari نوشته شده توسط: زبانهای مستقل از متن قطعی زیرمجموعه ای از زبانهای مستقل از متن غیرقطعین. همونطور که زبانهای منظم زیرمجموعه زبانهای مستقل از متن قطعین.الان یادم اومد نمودار زبان ها رو! :دی
ممنون
(۲۹ دى ۱۳۹۳ ۰۵:۰۱ ب.ظ)Farzamm نوشته شده توسط: خانواده زبان های مستقل از متن قطعی و غیرقطعی طبق تعریف، دو مجموعه کاملاً disjoint هستند.
مگه نمیشه یه زبان قطعی رو بصورت غیرقطعی نوشت؟ من با این فرض نوشتم.
(۲۹ دى ۱۳۹۳ ۰۵:۰۷ ب.ظ)Jooybari نوشته شده توسط: مگه نمیشه یه زبان قطعی رو بصورت غیرقطعی نوشت؟ من با این فرض نوشتم.
میشه نوشت ولی دلیل نمیشه که زبان غیرقطعی بشه
طبق تعریف، زبان مستقل از متنی قطعی است که بشه براش dpda کشید. یه زبان مستقل از متن یا dpda داره یا نداره.
(۲۹ دى ۱۳۹۳ ۰۵:۰۱ ب.ظ)Farzamm نوشته شده توسط: خانواده زبان های مستقل از متن قطعی و غیرقطعی طبق تعریف، دو مجموعه کاملاً disjoint هستند.تشکر
خانواده زبان های مستقل از متن قطعی زیرمجموعه زبان های مستقل از متن هست.
البته برای هر زبان مستقل از متن قطعی میشه گرامر غیرقطعی نوشت.
با سلام دوتا نکته البته تو این صحبت ها هست یک
گزینه اول که درسته چون زبان های مستقل از متن تحت مکمل گیری بسته نیستن.
این جمله کاملا غلطه ما از روی بسته بودن نتیجه میگیریم نه بسته نبودن زبان می تونه مستقل از متن باشه مکملش هم مستقل از متن باشه یا حتی منظم پس از روی بسته نبودن هیچ وقت نتیجه نمیگیریم
دو
برای هر زبان مستقل از متن قطعی میشه گرامر غیرقطعی نوشت؟
ما قطعی غیر قطعی بودن را روی گرامر مطرح نمی کنیم بلکه روی زبان و ماشین مطرح می کنیم روی گرامر صحبت مبهم و غیر مبهم بودن داریم والا من تا الان نشنیدم کسی بگه گرامر غیر قطعی یا قطعی تا جای که یادمه فکر کنم این حرفو دکتر کارگاهیم زدن البته یادم نیست دکتر کارگهی بودن یا نه ولی ما روی گرامر صحبت قطعی غیر قطعی بودن نمیکنیم اصولا
موفق باشید.
(۲۹ دى ۱۳۹۳ ۰۶:۵۸ ب.ظ)Hamid_0311 نوشته شده توسط: با سلام دوتا نکته البته تو این صحبت ها هست یکسلام
گزینه اول که درسته چون زبان های مستقل از متن تحت مکمل گیری بسته نیستن.
این جمله کاملا غلطه ما از روی بسته بودن نتیجه میگیریم نه بسته نبودن زبان می تونه مستقل از متن باشه مکملش هم مستقل از متن باشه یا حتی منظم پس از روی بسته نبودن هیچ وقت نتیجه نمیگیریم
خب وقتی گفته میشه زبان های مستقل از متن تحت مکمل گیری بسته نیستند، یعنی اگه یک زبان مستقل از متن رو مکمل کنیم، حاصل ممکنه مستقل از متن نباشه یا حتماً مستقل از متن نیست؟
یه سوال دیگه، اگه یک زبان مستقل از متن نباشه منظم هم نیست دیگه؟ درسته؟
تشکر
بله ما بسته بودن روی چی تعریف میکنیم؟ میگیم وقتی ۲ تا زبان مستقل از متنن اجتماعشون هم حتما مستقل از متنه
اما وقتی میگیم اشتراک دو زبان مستقل از متن بسته نیست یعنی اینکه ممکنه اشتراکشون مستقل از متن بشه ممکنه نشه پس از روی بسته نبودن ما نتیجه گیری نمی کنیم
بله وقتی مستقل از متن نباشه منظم هم نمی تونه باشه دیگه اگر منظم باشه که حتما مستقل از متنم هست
درسته، خیلی ممنونم.
