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

شمارا بودن یا نبودن زبانهای 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 نسبت به متمم بسته نیستن.
وچون بازگشتی ها زیر مجموعه بازگشتی شمارش پذیر هستن اینا هم شمارا هستن.



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  تفاوت classification algorithm و regression algorithm چیه؟ sajadg ۶ ۹,۰۸۴ ۱۵ خرداد ۱۴۰۰ ۰۱:۴۳ ب.ظ
آخرین ارسال: cyruskingsolomon
  همکار در حوزه speech recognition و برنامه نویسی اندروید pasargad7788 ۰ ۱,۹۵۰ ۳۱ خرداد ۱۳۹۹ ۰۹:۰۶ ب.ظ
آخرین ارسال: pasargad7788
Wink دانلود نظریه زبانهای پیتر لینز ویرایش ۵ + حل armin.sheikh ۵ ۱۱,۳۵۶ ۰۲ خرداد ۱۳۹۹ ۰۸:۲۶ ب.ظ
آخرین ارسال: gillda
  اثبات بومی بودن sirvan.t ۸ ۵,۱۴۸ ۱۰ اسفند ۱۳۹۸ ۰۹:۴۶ ب.ظ
آخرین ارسال: WILL
  رفع خطای Prevent saving changes that require ... در sql server deldar ۰ ۱,۷۰۵ ۲۴ مهر ۱۳۹۸ ۰۲:۴۹ ب.ظ
آخرین ارسال: deldar
  هیتلر بودن یا نبودن marvelous ۲ ۲,۴۹۲ ۰۴ مهر ۱۳۹۸ ۰۱:۴۱ ق.ظ
آخرین ارسال: marvelous
  حتماحتما بخوانید درموردافضل بودن امیرالمومنین هستش seyed ehsn ۱ ۲,۹۳۳ ۲۱ فروردین ۱۳۹۸ ۱۱:۰۹ ق.ظ
آخرین ارسال: banihashem
  در دسترس نبودن سایت negarin_ ۳ ۳,۳۴۰ ۱۵ آبان ۱۳۹۷ ۱۲:۱۹ ب.ظ
آخرین ارسال: negarin_
Question ارتباط real time نرم افزار اندرویدی با سرور اینترنت ic.chitgar ۱ ۲,۲۰۶ ۲۹ خرداد ۱۳۹۷ ۰۱:۴۱ ب.ظ
آخرین ارسال: nasimnami
  میزان سنگین بودن ارشد چقدره؟ (دوستانی که ارشد اند یا تموم شده ارشدشون) ya3ya6 ۴ ۳,۰۱۴ ۱۳ خرداد ۱۳۹۷ ۰۱:۴۶ ب.ظ
آخرین ارسال: Happiness.72

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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