سلام
۱-آیا مجموعه زبانهای بازگشتی (R ) شمارا هستند؟
۲-آیا مجموعه زبانهای بازگشتی فهرست پذیر(RE) شمارا هستند؟
سلام
اگه دقت کرده باشی هر قاعده ماشین تورینگ رو میشه به شکل باینری کد کرد.به این شکل که هر متغیرو به صورت مجموعه ایی از یکها در نظر میگیرن.وهر عملگرو یه صفر.به این صورت هر قاعده به شکل یه کد باینری میشه که متناظر یک عدد طبیعی هست.هر مجموعه ایی که متناظر با اعداد طبیعی باشه شماراست. پس هر زبانی که واسش گرامر داریم شماراست.چون زیر مجموعه محض اعداد طبیعی هست.زبانهای REزبانهای تشخیص پذیر هستن که واسشون ماشین تورینگ لزوما با حالت توقف نداریم .اینا بزرگترین مجموعه زبانهای صوری هستن.وچون واسشون گرامر صوری داریم شمارا هستن.زبانهای بازگشتی تصمیم پذیر rهستن که لزوما براشون ماشین تورینگ با توقف حالت نهایی داریم.یعنی زیر مجموعه زبانهای بازگشتی شمارش پذیر هستن.پس اینا هم شمارا هستن.
هر زیر مجموعه زبانهایREکه منظم ,مستقل ازمتن ,حساس به متن,بازگشتی تصمیم پذیر شماراست.
تو کتاب پوران این جمله نوشته شده:
مجموعه R شمارش ناپذیر است.
یعنی اشتباه نوشته دیگه؟درسته؟
صد درصد اشتباه مجموعه زبانهای صوری شمارا هستن.میتونی تو لینز هم ببینی.اما متمم REچون ممکنه بیفته بیرون مجموعه زبانهای صوری دیگه شمارا نیست.یعنی زبانهای تشخیص پذیر یا RE نسبت به متمم بسته نیستن.
وچون بازگشتی ها زیر مجموعه بازگشتی شمارش پذیر هستن اینا هم شمارا هستن.
(۱۰ بهمن ۱۳۹۳ ۰۵:۰۸ ب.ظ)software94 نوشته شده توسط: صد درصد اشتباه مجموعه زبانهای صوری شمارا هستن.میتونی تو لینز هم ببینی.اما متمم Rچون ممکنه بیفته بیرون مجموعه زبانهای صوری دیگه شمارا نیست.یعنی زبانهای تشخیص پذیر یا R نسبت به متمم بسته نیستن.
سلام دوست عزیز software94
به نظر شما مفهوم R و RE رو جابه‌جا متوجه شده‌اید!
R یا بازگشتی، زیرمجموعه‌ی RE یا به‌طور بازگشتی شمارا می‌باشد.
چون مکمل R هم بازگشتی است، می‌توان ماشین تورینگی طراحی کرد که هم عضویت و هم عدم عضویت هر رشته از زبان را اعلام کند (یعنی تصمیم گیری و توقف).
در مورد جواب سؤال اصلی هم دقت کنید که:
فهرست پذیر و شمارا به یک معنی هستند!
با این توصیفات مشخصه که هر دو شمارا هستند.
بله درسته.ببخشید یه لحظه اسامیشونو اشتباه کردم.
(۱۰ بهمن ۱۳۹۳ ۰۵:۰۳ ب.ظ)pooyaa نوشته شده توسط: تو کتاب پوران این جمله نوشته شده:
مجموعه R شمارش ناپذیر است.
یعنی اشتباه نوشته دیگه؟درسته؟
بستگی داره منظورش از R چی باشه ممکنه منظورش مجموعه ی اعداد حقیقی باشه که ناشماراست
معمولا مجموعه ی زبان های بازگشتی رو با Rec و مجموعه ی اعداد حقیقی رو با R نشون می دن