در این درس با سه موضوع “زبان، گرامر و
ماشین” آشنا می شوید. این درس پیش نیاز درس طراحی کامپایلر است. با یادگیری
زبان ها و گرامرها می توانید نحوه کار کامپایلر و همچنین طراحی زبان های
برنامه سازی را متوجه شد. یادگیری این درس بدون مدرس کار ساده ای نمی باشد و
ما در این آموزش تجربه حداقل پانزده سال تدریس این درس را در اختیار شما
گذاشته ایم. به امید اینکه دعای خیری برای ما شود.
فهرست سرفصل ها و رئوس مطالب مطرح شده
- فصل ۱ : عبارت منظم – زبان منظم
- عبارت منظم
- زبان
- اجتماع و اشتراک
- اتصال
- معکوس
- مکمل
- بستار
- هم ریختی
- تقسیم راست
- زبان منظم
- بسته بودن زبان های منظم
- لم تزریق
- فصل ۲ : گرامر – گرامر منظم
- گرامر
- انواع گرامر
- زبان تولید شده توسط گرامر
- گرامر منظم
- فصل ۳ : اتوماتای متناهی (DFA, NFA)
- انواع ماشین
- ماشین های متناهی
- پذیرنده متناهی معین (DFA)
- زبان ها و DFA ها
- حالت دام (تله)
- مکمل DFA
- پذیرنده متناهی نامعین ( NFA)
- هم ارزی DFA و NFA
- ارتباط گرامر منظم با ماشین متناهی
- کاهش تعداد حالات در ماشین های متناهی
- نحوه تشخیص منظم بودن یک زبان
- فصل ۴ : زبان و گرامر مستقل از متن
- گرامر مستقل از متن
- گرامر ساده
- بسته بودن زبان های مستقل از متن
- لم تزریق برای زبان های مستقل از متن
- لم تزریق برای زبان های خطی
- فصل ۵ : ابهام – ساده سازی گرامر – فرم های نرمال
- ابهام در گرامر و زبان
- ساده سازی گرامرهای مستقل از متن
- حذف متغیرها و قوانین بی فایده
- حذف قوانین
- حذف قوانین واحد
- فرم های نرمال گرامر مستقل از متن
- فرم نرمال چامسکی
- فرم نرمال گریباخ
- فصل ۶ : اتوماتای پشته ای (DPDA, NPDA)
- اتوماتای پشته ای نامعین
- تابع انتقال
- پیکر بندی لحظه ای
- اتوماتای پشته ای معین
- تشخیص مستقل از متن بودن یک زبان
- زبان مستقل از متن معین
- ساخت اتوماتای پشته ای با استفاده از گرامر در فرم گریباخ
- فصل ۷ : ماشین های تورینگ (TM)
- ماشین تورینگ استاندارد
- ماشین تورینگ در نقش پذیرنده زبان
- ماشین تورینگ به عنوان مترجم
- مدل های دیگر ماشین تورینگ
- سکون دار
- با نوار نیمه نامتناهی
- آف لاین
- با حافظه پیچیده تر
- چند نواره
- چند بعدی
- نامعین
- آتاماتای کراندار خطی (LBA)
- فصل ۸ : زبان های بازگشتی – گرامر بدون محدویت و حساس به متن
- زبان های بازگشتی و بازگشتی شمارش پذیر
- گرامر بدون محدودیت
- گرامر حساس به متن
- ارتباط بین زبان ها، گرامرها و ماشین ها
- سلسله مراتب چامسکی
- بررسی بسته بودن زبان ها تحت عملگرها
- فصل ۹ : تصمیم پذیری – کاهش پذیری
- زبان های تصمیم نا پذیر
- زبان های تصمیم پذیر
- تصمیم پذیری در زبان های منظم
- برشمارنده
- کاهش پذیری