هر
عبارت منظم یک زبان منظم را نشان میدهد!
گرامری
منظم است که یا خطی راست باشد و یا خطی
چپ.(و
همزمان هر دو نباشد)
گرامر
خطی گرامی است که هر یک قواید آن یا خطی
راست باشند و یا خطی چپ.
زبانهای
منظم و گرامرهای منظم هم ارزند!
زبانهای
خطی راست و زبانهای منظم و همچنین زبانهای
خطی چپ و زبانهای منظم هم ارزند!
۱.
اجتماع
متناهی.
۲.
اشتراک
۳.
الحاق
۴.
مکمل
۵.
بستار
ستاره.
۶.
معکوس.
۷.
همریختی
۸.
تقسیم
راست و چپ.
۹.
تحت
Nor
۱۰.
جفت
مکمل
۱۱.
تفاضل
متقارن
۱۲.
اگر
اجتماع دو زبان منظم باشد و یکی از آنها
متناهی باشی دیگری حتما منظم است اما اگر
متناهی نباشد لزوما درست نیست.
۱۳.
تحت
shuffle
و
exchange
زبانهای
منظم دارای الگوریتم عضویت و الگوریتم
تهی بودن و الگوریتم متناهی بودن و الگوریتم
تعیین تساوی میباشند.
لم
تزریق نمیتواند ثابت کند زبان منظم است.
تنها
اگر زبان نامنظم باشد آنرا ثابت میکند.
در
لم تزریق میتوان به سر و ته رشته انتخابی
هر رشته ای اضافه کرد(باید
رشته حاصله همچنان عضو زبان باشد)
و
باز هم لم تزریق درست است.
تمام
زبانهای متنهای(هرچقدر
بزرگ)
منظم
اند.
بطور
کلی زبانهایی که حالتهای خاص برای توان
در نظر میگیرند که نیاز به محاسبات
دارد(مثلا
اول بودن)
منظم
نیستند ولی حالتهای عمومی(مثلا
مضرب دو بودن یا به پیمانه ۳ برابر یک
بودن)
منظم
هستند.
زبانهایی
که چند الفبا دارند و رابطه توان الفبای
آنها به هم وابسته است منظم نیستند.
ممکن
است اجتماع دو زبان نا منظم زبانی منظم
باشد.
تنها
حالت معروفی که زبانهای منظم تحت آن بسته
نیستند اجتماع نامتناهی است.
بطور
کلی اکثر تحت اکثر عملیاتها زبانهای منظم
بسته اند و همچنین اکثر الگوریتمها براشون
وجود داره.
چیزهایی
که باید از کتاب خوانده شود:عبارت
منظم.
تعریف
زبان منظم مرتبط با عبارت منظم.
گرافهای
انتقال تعمیم یافته.
روال
تبدیل nfa
به
rex.
گرامرهای
خطی از راست و خطی از چپ.
تقسیم.
همریختی.
تفاضل
متقارن.
لم
تزریق زبانهای منظم.
هیچ نظری موجود نیست:
ارسال یک نظر