زمان کنونی: ۰۲ آبان ۱۳۹۸, ۰۴:۲۷ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

شمارا بودن یا نبودن زبانهای R و RE

ارسال:
  

pooyaa پرسیده:

شمارا بودن یا نبودن زبانهای R و RE

سلام

۱-آیا مجموعه زبانهای بازگشتی (R ) شمارا هستند؟
۲-آیا مجموعه زبانهای بازگشتی فهرست پذیر(RE) شمارا هستند؟

۴
ارسال:
  

MShariati پاسخ داده:

RE: دوتا سوال درمورد زبانهای R و RE

(۱۰ بهمن ۱۳۹۳ ۰۵:۰۸ ب.ظ)software94 نوشته شده توسط:  صد درصد اشتباه مجموعه زبانهای صوری شمارا هستن.میتونی تو لینز هم ببینی.اما متمم Rچون ممکنه بیفته بیرون مجموعه زبانهای صوری دیگه شمارا نیست.یعنی زبانهای تشخیص پذیر یا R نسبت به متمم بسته نیستن.

سلام دوست عزیز software94
به نظر شما مفهوم R و RE رو جابه‌جا متوجه شده‌اید!

R یا بازگشتی، زیرمجموعه‌ی RE یا به‌طور بازگشتی شمارا می‌باشد.
چون مکمل R هم بازگشتی است، می‌توان ماشین تورینگی طراحی کرد که هم عضویت و هم عدم عضویت هر رشته از زبان را اعلام کند (یعنی تصمیم گیری و توقف).

در مورد جواب سؤال اصلی هم دقت کنید که:
فهرست پذیر و شمارا به یک معنی هستند!
با این توصیفات مشخصه که هر دو شمارا هستند.

۲
ارسال:
  

software94 پاسخ داده:

RE: دوتا سوال درمورد زبانهای R و RE

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

۰
ارسال:
  

software94 پاسخ داده:

RE: دوتا سوال درمورد زبانهای R و RE

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

۰
ارسال:
  

pooyaa پاسخ داده:

RE: دوتا سوال درمورد زبانهای R و RE

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

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

ارسال:
  

fatemeh69 پاسخ داده:

RE: دوتا سوال درمورد زبانهای R و RE

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

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

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

۰
ارسال:
  

software94 پاسخ داده:

RE: دوتا سوال درمورد زبانهای R و RE

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  تشخیص قطعی بودن ۴ زبان مستقل از متن MR.oracle ۹ ۴,۰۵۸ ۱۲ بهمن ۱۳۹۳ ۱۲:۲۳ ب.ظ
آخرین ارسال: ریحان
  منظم بودن uww^R v nazanin2020 ۵ ۲,۳۲۶ ۱۱ بهمن ۱۳۹۳ ۱۰:۱۵ ب.ظ
آخرین ارسال: nazanin2020
  خانواده زبانهای منظم تحت اشتراک نامتناهی بسته هستند؟ pooyaa ۶ ۲,۲۲۸ ۰۸ بهمن ۱۳۹۳ ۰۴:۴۳ ب.ظ
آخرین ارسال: s4l34.jahed
  تشخیص مستقل از متن و قطعی بودن چند زبان mostafa2012 ۱۱ ۶,۰۱۳ ۰۵ بهمن ۱۳۹۳ ۰۶:۲۲ ب.ظ
آخرین ارسال: Hamid_0311
  علت منظم بودن زبان w v w^R archer22 ۲ ۱,۳۳۶ ۰۵ بهمن ۱۳۹۳ ۱۲:۰۰ ق.ظ
آخرین ارسال: archer22
  تشخیص مستقل از متن قطعی و عیر قطعی بودن ۶ زبان maryam.roshan ۴ ۱,۵۷۸ ۲۹ دى ۱۳۹۳ ۰۴:۳۵ ب.ظ
آخرین ارسال: Jooybari
  دلیل منظم و نامنظم بودن این دو زبان چیست؟ sana70 ۸ ۲,۵۷۵ ۱۰ دى ۱۳۹۳ ۱۰:۴۰ ب.ظ
آخرین ارسال: sana70
  بررسی بسته بودن خانواده ی زبان ها بر روی عملگر * m-kafiyan ۱ ۷۴۱ ۰۸ دى ۱۳۹۳ ۰۱:۰۰ ق.ظ
آخرین ارسال: fatemeh69
  اثبات مستقل از متن بودن a^mb^m alifarokhi ۱ ۹۴۵ ۲۸ آذر ۱۳۹۳ ۱۰:۵۶ ب.ظ
آخرین ارسال: Hamid_0311
  اثبات مستقل از متن بودن ww^R alifarokhi ۲ ۱,۰۹۶ ۲۸ آذر ۱۳۹۳ ۱۰:۳۹ ب.ظ
آخرین ارسال: Hamid_0311

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close