نکات تستی کنکور نظریه زبانها - سلسله مراتب زبانها

زبان شمارش پذیر بازگشتی کلی تر از زبان بازگشتی است. در واقع زبان بازگشتی تنها شامل آنهایی میشود که الگوریتم عضویت داشته باشند.

زبان بازگشتی شمارش پذیر است.

به ازای هر الفبای غیر تهی زبانهایی وجود دارند که شمارش پذیر بازگشتی نیستند(مثلا مجموعه توانی یک مجموعه شمارش پذیر بازگشتی)

خانواده زبانهای شمارش پذیر بازگشتی تحت مکمل بسته نیست.

خانواده زبانهای شمارش پذیر بازگشتی تحت اجتماع و معکوس و تفریق بازگشتی بسته است.

خانواده زبانهای شمارش پذیر تحت اجتماع و اشتراک و معکوس و بستار بسته است.

زبانهایی وجود دارد که شمارش پذیر بازگشتی هستند اما بازگشتی نیستند.

اگر زبان L و مکمل آن شمارش پذیر بازگشتی باشند آنگاه حتما بازگشتی هستند و اگر زبان L بازگشتی باشد آنگاه مکمل آن هم بازگشتی است و در نتیجه هر دو شمارش پذیر بازگشتی هستند.

مجموعه تمام اعداد حقیقی شمارش پذیر نیست.

مجموعه تمام زبانهایی که شمارش پذیر بازگشتی نیستند قابل شمارش نمیباشد.

اگر L یک زبان مستقل از متن باشد آنگاه L+ شمارش پذیر بازگشتی است.

گرامر بدون محدودیت زبانهای شمارش پذیر بازگشتی تولید میکند و برعکس.

توجه شود در سمت چپ گرامر بدون محدودیت لاندا نمیتواند وجود داشته باشد(این محدودیت رو داره)

زبانهای حساس به متن با اتوماتای کراندار خطی lba هم ارز هستند

زبانهای حساس به متن بازگشتی هستند ولی همه زبانهای بازگشتی حساس به متن نیستند.

ترتیب زبانها بصورت زیر است:(علامت < به معنی زیر مجموعه بودن است)

منظم(سطح ۳)< مستقل از متن معین(سطح ۲) < مستقل از متن(سطح ۲)< وابسته به متن(سطح ۱) <‌بازگشتی(سطح ۰) <بازگشتی شمارش پذیر(سطح ۰)

زبانهای منظم زیر مجموعه اشتراک زبانهای مستقل از متن قطعی و زبانهای خطی هستند(که هر دو اینها زیر مجموعه زبانهای مستقل از متن هستند)

چیزهایی که باید از کتاب خوانده شود: زبانهای بازگشتی و شمارش پذیر بازگشتی. گرامر بدون محدودیت. گرامرهای حساس به متن.