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

Theory of Machines and Languages

شماره درس: ۴۰۴۱۵	تعداد واحد: ۳
مقطع: کارشناسی	نوع درس: نظری
پیش‌نیاز: ساختمان داده‌ها و الگوریتم‌ها	هم‌نیاز: –

اهداف درس

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

ریز مواد

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

ارزیابی

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

مراجع

M. Sipser. Introduction to the Theory of Computation. 3rd Edition, Cengage Learning, 2013.
P. Linz. An introduction to formal languages and automata. 3rd Edition, Jones and Bartlett Publishers, 2001.
J. E. Hopcroft, R. Motwani, and J. D. Ullman. Introduction to automata theory, languages, and computation. 2nd Edition, Addison-Wesley, 2001.
J. P. Denning, J. B. Dennis, and J. E. Qualitz. Machines, languages, and computation. Prentice-Hall, 1978.
J. E. Hopcroft and J. D. Ullman. Introduction to automata theory, languages, and computation. Addison-Wesley, 1979.
P. J. Cameron. Sets, Logics and Categories. Springer, 1998.