با سلام خدمت عزیزان
با توجه به اینکه ماشین M یک ماشین تورینگ باشه. عبارات زیر تصمیم پذیر هستند یا تصمیم ناپذیر؟ دلیلش رو هم بگین ممنون میشم
- آیا L(M دو رشته به طول مساوی دارد یا نه
- آیا L(M منظم هست یا نه
اگر L یک زبان منظم و L(G یک زبان مستقل از متن باشه اونوقت L(G)=L تصمیم پذیره یا نه؟
ممنون و متشکر
(۱۲ بهمن ۱۳۹۲ ۱۲:۳۴ ب.ظ)hosshah نوشته شده توسط: با سلام خدمت عزیزانخیلی تو این زمینه تحلیل ندارم ولی نظر من اینه
با توجه به اینکه ماشین M یک ماشین تورینگ باشه. عبارات زیر تصمیم پذیر هستند یا تصمیم ناپذیر؟ دلیلش رو هم بگین ممنون میشم
- آیا L(M دو رشته به طول مساوی دارد یا نه
- آیا L(M منظم هست یا نه
اگر L یک زبان منظم و L(G یک زبان مستقل از متن باشه اونوقت L(G)=L تصمیم پذیره یا نه؟
ممنون و متشکر
هیچکدوم از اون چیزایی که گفتی تصمیم پذیر نیست
واسه منظم ها ، هر چی بگی تصمیم پذیره
واسه مستقل ، عضویت ، تهی بودن، و نا متناهی بودن تصمیم پذیره
واسه حساس و بازگشتی مسئله عضویت تصمیم پذیره ، ظاهرا حساس یه چیز دیگه هم داره ولی یادم نیس
واسه بازگشتی شمارا هیچی تصمیم پذیر نیست. تورینگ هم همون بازگشتی شمارا محسوب میشه
البته یه سری استثنا های عجیبی وجود داره که من نفهمیدم چی هست و صحبتی هم در موردش نمیکنم چون میترسم هم خودم گیج بشم و هم شما
مثلا آیا ماشین تورینگ در حرکتهاش ، به سمت چپ میره یا نه تصمیم پذیره (فکر کنم پوران گفته بود) ولی اینکه در ماشین تورینگ هد آیا از سمت چپ رشته میزنه بیرون تصمیم پذیر نیست
خیلی ممنون از جوابت دوست عزیز
الان در مورده سوال دومم واسه این میگین تصمیم ناپذیره چون دامنه نامتناهی هستش؟ مثلا تساوی دو زبان منظم نامتناهی قابل تصمیم گیریه؟ چون اگر متناهی باشن خب مسلما تصمیم پذیره
در مورد زبان های RE هم اگر یه خصوصیت non-trivial باشه تصمیم ناپذیره اما مثلا عمل Reverse تصمیم پذیره
در ضمن در مورد تصمیم پذیر بودن یا نبودن اون مسائلی که مطرح کردین به عقیده من که تصمیم پذیر نیستن چون میشه مسائل تصمیم ناپذیر رو به این ها Reduce کرد
این بحثا واقعا پیچیده ست و خیلی بحث میخواد
(۱۲ بهمن ۱۳۹۲ ۰۱:۲۹ ب.ظ)hosshah نوشته شده توسط: خیلی ممنون از جوابت دوست عزیزکار داره به جاهای باریک میکشه . یه کم بحث زیادی خفن شد . دیگه از عهده من خارج شد
الان در مورده سوال دومم واسه این میگین تصمیم ناپذیره چون دامنه نامتناهی هستش؟ مثلا تساوی دو زبان منظم نامتناهی قابل تصمیم گیریه؟ چون اگر متناهی باشن خب مسلما تصمیم پذیره
در مورد زبان های RE هم اگر یه خصوصیت non-trivial باشه تصمیم ناپذیره اما مثلا عمل Reverse تصمیم پذیره
در ضمن در مورد تصمیم پذیر بودن یا نبودن اون مسائلی که مطرح کردین به عقیده من که تصمیم پذیر نیستن چون میشه مسائل تصمیم ناپذیر رو به این ها Reduce کرد
این بحثا واقعا پیچیده ست و خیلی بحث میخواد
non-trivial ؟؟؟
این همون قضیه Rice هستش
میگه اگر یه صفت بدیهی نباشه در مورد RE ها تصمیم ناپذیره. حالا به صفتی میگیم غیر بدیهی که برای همه زبان های RE برقرار نباشه
مثلا عبارته زیر non-trivial هستش
[tex]L(M_{1})\subseteq L(M_{2})[/tex]
چرا؟ چون اگه برای همه زبان های RE این عبارت رو میتونستیم تصمیم بگیریم اونوقت تساوی دو تا زبان RE تصمیم پذیر میشد
(۱۲ بهمن ۱۳۹۲ ۰۲:۲۳ ب.ظ)hosshah نوشته شده توسط: نه بابا هممون تو یه حدیم اگه شما بالاتر نباشیآهان. رایس، همون برنج خودمون.
این همون قضیه Rice هستش
میگه اگر یه صفت بدیهی نباشه در مورد RE ها تصمیم ناپذیره. حالا به صفتی میگیم غیر بدیهی که برای همه زبان های RE برقرار نباشه
مثلا عبارته زیر non-trivial هستش
[tex]L(M_{1})\subseteq L(M_{2})[/tex]
چرا؟ چون اگه برای همه زبان های RE این عبارت رو میتونستیم تصمیم بگیریم اونوقت تساوی دو تا زبان RE تصمیم پذیر میشد
خوف کردم یه لحظه که این دیگه چیه
آها همون برنج ایول
حالا اون دوتایی که اون اول گفتی تصمیم ناپذیرن دیگه؟؟
(۱۲ بهمن ۱۳۹۲ ۰۲:۳۰ ب.ظ)hosshah نوشته شده توسط: آها همون برنج ایولبله قربونت. برنج هند آفت نداره
حالا اون دوتایی که اون اول گفتی تصمیم ناپذیرن دیگه؟؟
اون دوتا تصمیم ناپذیرند. برای اینکه مطمئن هم بشم یه نگاه دیگه به منبع غیر معتبر پوران اندختم که خیالت هم راحت باشه
دیگه فعلا این هادی یوسفی و مقسمی دارن جلون میدن (به املا زیاد دقت نکن) تازگی ها هم که ارسطو خلیلی فر بهشون اضافه شده
دم شما گرم مرسی موفق باشی