برای
هر زبان مستقل از متن یک اتوماتای پشته
ای وجود دارد و برعکس.
به
ازای هر npda
یک
npda
معادل
با حداکثر سه حالت وجود دارد.
از
این لم تزریق ها هم فقط برای اثبات عدم
تعلق زبان به آن مجموعه میتوان استفاده
نمود.
تفاوت
لم تزریق منظم و خطی و مستقل از متن:
در
منظم w=xyz
بود
و شروط xy<m
و
y>1
را
داشتیم در خطی w=uvxyz
است
و شروط uvyz<m
و
vy>1
را
داریم و در مستقل از متن هم w=uvxyz
بود
و شروط vxy<m
و
vy>1
را
داریم.
به
ازای هر زبان خطی فاقد لاندا یک گرامر خطی
فاقد لاندا و قانون واحد وجود دارد.
خانواده
زبانهای مستقل از متن تحت اعمال زیر بسته
است:
۱.
اجتماع.
۲.
الحاق.
۳.
بستار
ستاره.
۴.
اشتراک
با یک زبان منظم.
۵.
همریختی.
۶.
تفاضل
منظم.
خانواده
زبانهای مستقل از متن تحت اعمال زیر بسته
نیست:
۱.
اشتراک
۲.
مکمل
گیری
۳.
تفاضل
برای
زبانهای مستقل از متن الگوریتم تصمیم
گیری برای تهی بودن و الگوریتم تعیین
متناهی بودن و عضویت لاندا در زبان و
الگوریتم وجود عضو مشترک بین دو زبان وجود
دارد.
زبانهای
مستقل از متن قطعی تحت تفاضل منظم بسته
است.
خانواده
زبانهای خطی تحت هم ریختی و اجتماع و الحاق
منظم بسته است و تحت الحاق و اشتراک بسته
نیست.
خانواده
زبانهای مستقل از متن غیر مبهم تحت اجتماع
و اشتراک بسته نیست.
چیزهایی
که باید از کتاب خوانده شود:
اتوماتای
پشته ای نامعین و معین.
زبان
مستقل از متن معین.
مبحث
LL(K)(البته
بطور کلی در کامپایلر بررسی میشود).
لم
تزریق زبانهای مستقل از متن.
زبانهای
خطی.
لم
تزریق زبانهای خطی.
لم
Ogden
هیچ نظری موجود نیست:
ارسال یک نظر