بخشی از پاورپوینت
اسلاید 1 :
نظريه زبان ها و ماشين ها
زبان های نامنظم
برای درک قدرت ماشين ها بايد محدوديت های آن ها را بشناسيم.
برخی از زبان ها را نمی توان با ماشين حالت متناهی تشخيص داد.
مثلاً برای تشخيص زبان زير بايد در حالت ها تعداد 0 ها را حفظ کنيم.
اما حالت های متناهی يک DFA پاسخگوی تعداد نامتناهی حالات ممکن نيست.
نياز به يک مبنای نظری برای اثبات منظم نبودن داريم: لم پامپينگ
اسلاید 2 :
لم پامپينگ
اسلاید 3 :
ايده اثبات
بنا به اصل لانه کبوتری، برای رشته هايی با بيش از اين طول، حداقل يک حالت در دنباله حالات تکرار می شود.
اسلاید 4 :
اثبات
اسلاید 5 :
مثال
با استفاده از لم پامپينگ و برهان خلف ثابت می کنيم که زبان زير منظم نيست:
چرا هيچ يک از سه حالت فوق نمی تواند درست باشد؟
اسلاید 6 :
مثال
با استفاده از لم پامپينگ و برهان خلف ثابت می کنيم که زبان زير منظم نيست:
در متن اصلی پاورپوینت به هم ریختگی وجود ندارد. برای مطالعه بیشتر پاورپوینت آن را خریداری کنید
