نظریه زبان‌ها و ماشین‌ها

این درس درباره جنبه‌های نظری رشته مهندسی و علم کامپیوتر است. مباحث مورد بررسی شامل مدل‌های مختلف محاسباتی، توانایی محاسباتی این مدل‌ها، خواص محاسباتی آن‌ها و کاربردهای آن‌ها است. دیگر مباحث شامل مفاهیم محاسبه‌پذیری، تصمیم‌پذیری و تز چرچ و تورینگ در مورد الگوریتم‌هاست.

• مباحث مقدماتی (۴ جلسه)
  • منطق گزاره‌ای، منطق مسندی، سیستم اثبات، نظریه‌ی مجموعه‌ها، پارادُکس راسِل، مجموعه‌های شمارا و ناشمارا، زبا‌ن‌ها و گرامرها.
• ماشین‌های حالت متناهی (۸ جلسه)
  • پذیرنده‌های متناهی قطعی، پذیرنده‌های متناهی غیرقطعی، زبان‌های منظّم، عبارات منظّم، گرامرهای راستگرد خطّی، گرامرهای چپگرد خطّی، گرامرهای منظّم، گرامرهای خطّی، زبان‌های نامنظّم، لِم پُمپینگ برای زبان‌های منظّم.
• زبان‌های مستقل از متن (۱۰ جلسه)
  • گرامرهای مستقل از متن، زبان‌های مستقل از متن، اشتقاق چپگرد، اشتقاق راستگرد، درخت اشتقاق، گرامرهای مبهم، گرامرهای نامبهم، زبان‌های ذاتاً مبهم، زبان‌های نامبهم، ساده‌سازی گرامرهای مستقل از متن، گرامرهای مستقل از متن به صورت طبیعی چامسکی، گرامرهای مستقل از متن به صورت طبیعی گرایباخ، مسأله عضویت، الگوریتم CYK، ماشین‌های پوش دان، هم ارزی ماشین‌های پوش دان و گرامرهای مستقل از متن، ماشین‌های پوش دان قطعی، زبان‌های مستقل از متن قطعی، زبان‌های غیر مستقل از متن، لِم پُمپینگ برای زبان‌های مستقل از متن.
• محاسبه‌پذیری (۸ جلسه)
  • ماشین تورینگ، تِز چِرچ و تورینگ، تصمیم‌پذیری و تصمیم‌ناپذیری، محاسبه‌پذیری و محاسبه‌ناپذیری، مسئله توقّف، مسئله تخصیص پُست، پیچیدگی محاسباتی، رده پیچیدگی P، رده پیچیدگی NP، مسائل NP کامل، مسائل NP سخت.

• تمرینات هفتگی (۳۰٪)
• کوییزها (۴۵٪)
• آزمون پایان نیم‌سال (۲۵٪)