بله درسته.ببخشید یه لحظه اسامیشونو اشتباه کردم.

سلام
اگه دقت کرده باشی هر قاعده ماشین تورینگ رو میشه به شکل باینری کد کرد.به این شکل که هر متغیرو به صورت مجموعه ایی از یکها در نظر میگیرن.وهر عملگرو یه صفر.به این صورت هر قاعده به شکل یه کد باینری میشه که متناظر یک عدد طبیعی هست.هر مجموعه ایی که متناظر با اعداد طبیعی باشه شماراست. پس هر زبانی که واسش گرامر داریم شماراست.چون زیر مجموعه محض اعداد طبیعی هست.زبانهای REزبانهای تشخیص پذیر هستن که واسشون ماشین تورینگ لزوما با حالت توقف نداریم .اینا بزرگترین مجموعه زبانهای صوری هستن.وچون واسشون گرامر صوری داریم شمارا هستن.زبانهای بازگشتی تصمیم پذیر rهستن که لزوما براشون ماشین تورینگ با توقف حالت نهایی داریم.یعنی زیر مجموعه زبانهای بازگشتی شمارش پذیر هستن.پس اینا هم شمارا هستن.
هر زیر مجموعه زبانهایREکه منظم ,مستقل ازمتن ,حساس به متن,بازگشتی تصمیم پذیر شماراست.

تو کتاب پوران این جمله نوشته شده:
مجموعه R شمارش ناپذیر است.

یعنی اشتباه نوشته دیگه؟درسته؟

(۱۰ بهمن ۱۳۹۳ ۰۵:۰۳ ب.ظ)pooyaa نوشته شده توسط:  تو کتاب پوران این جمله نوشته شده:
مجموعه R شمارش ناپذیر است.

یعنی اشتباه نوشته دیگه؟درسته؟

بستگی داره منظورش از R چی باشه ممکنه منظورش مجموعه ی اعداد حقیقی باشه که ناشماراست
معمولا مجموعه ی زبان های بازگشتی رو با Rec و مجموعه ی اعداد حقیقی رو با R نشون می دن

صد درصد اشتباه مجموعه زبانهای صوری شمارا هستن.میتونی تو لینز هم ببینی.اما متمم REچون ممکنه بیفته بیرون مجموعه زبانهای صوری دیگه شمارا نیست.یعنی زبانهای تشخیص پذیر یا RE نسبت به متمم بسته نیستن.
وچون بازگشتی ها زیر مجموعه بازگشتی شمارش پذیر هستن اینا هم شمارا هستن.