اگر کسی از دوستان مبحث بازگشتی و برشمارش بازگشتی رو خوب متوجه شده یه توضیحی در موردش بده.
به نظر من یکی از مباحث گنگ نظریه اس
چند بار تاحالا خوندمش ولی مطالبش چون حفظیه یادم میره.
اگر هر کس یه نکته هم بگه شاید اینطور راحت‌تر بشه فهمیدش
مرسییییی
بازگشتی: یعنی وقتی یک رشته به ماشین میدهیم متوقف شود و اگر عضو زبان است بله و اگر عضو زبان نیست خیر را به ما بدهد یعنی پس از توقف مشخص شود که رشته عضو زبان هست یا خیر (در حلقه بینهایت نمی افتد)
بازگشتی برشمردنی: به ازای رشته هایی که عضو زبان هستند متوقف شود و بگوید بله این رشته عضو زبان هست.
اما در مورد رشته هایی که عضو زبان نیستند ممکن است متوقف نشود.(مثلا در حلقه بینهایت بیفتد)
شاید بگویید خوب اگر یک رشته متوقف نشد بگوییم عضو زبان نیست( اما ممکن است مثلا اگر اندکی دیگر صبر میکردیم متوقف میشد و میفهمیدیم عضو زبان است)
مثلا وقتی میروید خودپرداز و خودپرداز ۱۵ دقیقه است که نوشته صبر کنید شما نمیدانید که پول را پرداخت میکند یا خیر ممکن است ۱ دقیقه دیگر متوقف شود یا هیچ وقت متوقف نشود اما شما به طور قطع نمیتوانید بگویید که دستگاه متوقف نمیشود یا میشود مگر بعد از اینکه دستگاه متوقف شد و پول شما را داد.
البته خودم هم سر جلسه آزمون یادم رفته بود کدوم شمارا بود و همه تستهاشو غلط زدم: دی
چه تعریف های جالبی
او هیچ کتابی ندیدم اینطوری گفته باشه ولی خب اینا چه کمکی می تونه بکنه به تست زدن و چطور میشه با استفاده از این تعریف‌ها خواص این زبانها را فهمید؟
مثلا اینکه خانواده زبان های بازگشتی زیر مجموعه سره ای ازخانواده زبان های برشمارش بازگشتی است.
من که رابطه ای بینشون پیدا نکردم!
اگر رشته‌ای به ماشین تورینگ زبانهای بازگشتی بدهیم در پایان کار یا رشته را قبول میکنه (پذیرش رشته )یا رشته را رد میکنه
اگر رشته‌ای به ماشین زبانهای بازگشتی شمارشی بدهیم اگر جز زبان باشد قبول میکنه ولی اگر نباشه هیچ جوابی نمیده
پس زبانهای بازگشتی قبول و رد دارند ولی زبانهای بازگشتی شمارشی فقط قبول را دارند بنابراین زبانهای که امکان داره جز زبانهای بازگشتی نبوده، چز زبانهای بازگشتی شمارشی باشه شاید هم حتی جز زبانهای بازگشتی شمارشی نباشه. ولی اگر زبان چز زبانهای بازگشتی شمارشی باشد پس حتما میتونه چز زبانهای بازگشتی نیز باشد.
خوب اینکه زبانهای بازگشتی زیر مجموعه زبانهای بازگشتی شمردنی است به این خاطره که زبانهای بازگشتی برای رشته ای که عضو این زبان است متوقف میشوند و جواب بله میدهند (فعلا با بقیه اعضا کاری نداریم) و این همان تعریف بازگشتی برشمردنی است.
ولی برعکسش درست نیست چون یک زبان برشمردنی برای رشته ای که عضوش نیست توقف نمیکند پس بازگشتی نیست چون بازگشتی‌ها برای همه رشته‌ها متوقف میشوند.
من فکر میکنم اگه شما این مفهوم رو کاملا درک کنید( منظورم این مفهوم که بازگشتی‌ها به ازای همه رشته‌ها متوقف میشوند ولی شمردنی‌ها الزاما برای رشته هایی که عضو این زبانند متوقف میشوند.)
همه تستها رو میتونید بزنید.
بسیار دقیق و تمیز گفتی آفاق ممنونتم
در مورد شمارا بودن یا نبودن لطفا اگه بلدید هم بگین
مثلا مجموعه کل زبانها شمارش ناپذیرند
مجموعه Nشمارش پذیر نامتناهی و اینا هی یادم میره چون کامل درک نکردم
خواهش میکنم :دی
شمارش پذیر متناهی نا متناهی و اینااااا!
اگر رشته های زبان ترتیب داشته باشند میشه شمارا. یعنی بر یه اساسی بشه مرتبشون کرد مثلا بر اساس حروف الفبا.
متناهی و نامتناهی هم که بحث های ریاضی هستند خوب اگه بی نهایت تا رشته باشند میشه نامتناهی اما اگه تعدادشون محدود باشه میشه متناهی. مثلا اگه بگیم n<=100 متناهیه و مثلا +a نامتناهیه.
+a نامتناهی و شماراست چون هم بینهایت رشته است و هم میشه مرتب نوشتشون:
a,aa,aaa,aaaa
الی آخر
میشه در مورد متمم این زبانها هم توضیح بدید؟ این که مثلا متمم بازگشتی، بازگشتی هست یا نه؟؟ شمارش پذیر بازگشتی چطور؟ هست یا نه؟
در مورد بازگشتی شمارش پذیر هم آیا متممش هم بازگشتی شمارش پذیر هست؟ یا بازگشتی؟
زبانهای بازگشتی برشمردنی تحت متمم بسته نیست.
اما تحت اجتماع اشتراک الحاق بستار ستاره و معکوس کردن بسته است.
زبانهای بازگشتی تحت متمم، اجتماع اشتراک اتصال بستارستاره معکوس کردن وتفاضل بسته است.
یه نکته جالب: اگر یک زبان هم خودش و هم متمم اش بازگشتی برشمردنی باشند آن زبان بازگشتی است.
میشه راجع به ارتباط بین زبانهای بازگشتی و بازگشتی شمارش پذیر با مجموعه های شمارا و ناشمارا هم توضیح بدید؟
مجموعه شمارا یعنی اینکه بتونیم رشته های یک زبان رو بر اساس مثلا حروف مرتب کنیم.
مثلا a,aa,aaa شماراست.
اگه اعضای زبان ترتیب خاصی نداشته باشن میشه ناشمارا.