چطور میشه فهمید یه زبان تصمیم پذیر-بازگشتی-شمارش پذیر است؟
(۰۴ بهمن ۱۳۹۱ ۱۱:۳۸ ب.ظ)یگانه نوشته شده توسط: چطور میشه فهمید یه زبان تصمیم پذیر-بازگشتی-شمارش پذیر است؟
زبانی شمارش پذیر بازگشتی هست اگر ماشین تورینگی باشه که آن زبان را بپذیره، رشته های عضو زبان رو بپذیره و yes بگه.
(۰۴ بهمن ۱۳۹۱ ۱۱:۵۴ ب.ظ)Shiny_Star نوشته شده توسط: زبانی شمارش پذیر بازگشتی هست اگر ماشین تورینگی باشه که آن زبان را بپذیره، رشته های عضو زبان رو بپذیره و yes بگه.منظورم این بود که تفاوت بین محاسبه پذیربودن،تصمیم پذیربودن ویا بازگشتی بودن یک زبان چیه؟
من توی تستایی که زدم اینجوری فهمیدم که هر زبان تصمیم پذیر بازگشتی است
و هر زبان بازگشتی تصمیم پذیر.البته مطمئن نیستم.
محاسبه پذیر بودن را هم نمیدونم.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
زبان های بازگشتی
در ریاضیات، منطق و علوم کامپوتر، زبان بازگشتی یک نوع زبان صوری است که همچنین بازگشتی، تصمیم پذیر یا تصمیم پذیر بازگشتی نامیده می شود.کلاس تمامی زبان های بازگشتی غالبا" R نامیده می شود، با اینکه این نام برای کلاس RP نیز استفاده می شود.
این نوع از زبان به طور واضحی از سلسله مراتب چامسکی(Chomsky hierarchy) جا مانده است.
تعاریف:
دو تعریف برابر و اصلی برای مفهوم زبان بازگشتی وجود دارد:
۱- یک زبان صوری بازگشتی یک زیر مجموعه بازگشتی(recursive subset)در مجموعه تمامی کلمات ممکن بر روی الفبای زبان است.
۲- یک زبان بازگشتی یک زبان صوری است که برایش ماشین تورینگی وجود دارد که، هنگامی که با یک رشته ورودی مواجه می گردد، متوقف می شود و اگر رشته در زبان موجود باشد آن را می پذیرد، در غیر این صورت متوقف می گردد و آن رشته را نمی پذیرد. ماشین تورینگ همیشه متوقف می گردد: این ماشین به عنوان تصمیم پذیر شناخته می شود.
تمامی زبان های بازگشتی بازگشتی برشمردنی نیز هستند. تمامی زبان های منظم، مستقل از متن وحساس به متن زبان های بازگشتی می باشند.
خواص بسته بودن:
زبان های بازگشتی برروی اعمال زیر بسته اند.یعنی، اگر زبان L و زبان P هر دو بازگشتی باشند، در نتیجه زبان های زیر نیز بازگشتی اند:
- ستاره L
- اتصال L وP
- اجتماع L وP
- اشتراک L وP
- اختلاف L وP
-------
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
طبق چیزی من میدونم زبانی که واسش رویه شمارش باشه تو رینگ هم هست واسش پس شمارش پذیر بازگشتیه!
هر زبانی شمارش پذیر بازگشتی باشه تورینگ واسش هست وبرعکس.
زبانی هست که شمارش پذیر بازگشت هست ولی بازگشتی نیست.ولی هر زبانی بازگشتی باشد هر زبانی !!! تاکید هر زبانی بازگشتی باشد شمارش پذیر بازگشتی هم هست
زبانی بازگشتیه که یه الگوریتم عضویت برای ان باشد مثلا لاندا عضو یه زبان مستقل از متن الگوریتم عضویت واسش وجود داره پس بازگشتیه
ولی ابهام زبانهای CNF مستقل از متن الگوریتم عضویت نداره پس بازگشتی هم نیست
اگر یه زبانی خودش و مکملش هر دو تاشون بازگشتی شمارش پذیر باشد حتما بازگشتی هم هست