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

در علوم نظری رایانه، نظریه اتوماتا یا ماشین‌ها به بررسی ماشین‌های محاسبه‌گر انتزاعی و قدرت آن‌ها در حل مسایل پرداخته خواهد شد. در این کلاس، درس نظریه زبان‌ها و ماشین‌ها در دوره کارشناسی مهندسی کامپیوتر و درس نظریه محاسبات در دوره کارشناسی علوم کامپیوتر به صورت کامل طبق مراجع اصلی این درس با رویکرد حل مسائل تدریس خواهد شد و جهت آمادگی بیشتر دانشجویان در کنکور مهندسی کامپیوتر و علوم کامپیوتر، تست‌های آزمون‌های کارشناسی ارشد این دو رشته در حین درس به جزئیات حل خواهد شد. 

منابع درسی: 
• کتاب مرجع، معرفی زبان‌های فرمال و آتوماتا نوشته پیتر لینز 
• کتاب مرجع، نظریه محاسبات نوشته مایکل سیپسر 
• کتاب مرجع، معرفی زبان ها و نظریه محاسبات نوشته مارتین 
• کتاب مرجع، معرفی نظریه آتوماتا، زبان‌ها و محاسبات نوشته هاپکرافت، موتوانی و اولمان 

سرفصل درس نظریه زبان‌ها و ماشین‌ها: 
• فصل اول: مقدمه‌ای بر نظریه محاسبات، مباحث پیشنیاز و مفاهیم اولیه نظریه‌ی مجموعه‌ها، اصول منطق، روش‌های اثبات، رابطه و تابع، مجموعه‌های شمارا و ناشمارا، مفاهیم پایه گراف و درخت، روابط بازگشتی، نمادهای مجانبی، الفبا، رشته، زبان‌، عملیات روی رشته‌ها و زبان‌ها، مدل بازگشتی، مختصری بر گرامرها، آتوماتا 
• فصل دوم: ماشین‌های حالت متناهی ماشین پذیرنده متناهی قطعی، ماشین پذیرنده متناهی غیرقطعی، تبدیل بین DFA وNFA ، ماشین DFA کمینه، ماشین‌ مترجم متناهی 
• فصل سوم: زبان‌های منظم عبارت‌های منظم، گرامرهای منظم، زبان‌های منظم و ارتباط بین این مدل‌ها 
• فصل چهارم: ویژگی‌های زبان‌های منظم خصوصیات بستاری زبان‌های منظم، تصمیم پذیری و خواص الگوریتمیک زبان‌های منظم، زبان‌های نامنظم، لم تزریق زبان‌های منظم، قضیه Myhill–Nerode، دیگر روش‌های تشخیص یک زبان منظم و خانواده‌های زبان‌های زیرمجموعه زبان‌های منظم 
• فصل پنجم: زبان‌های مستقل از متن گرامرهای مستقل از متن، زبان‌های مستقل از متن، اشتقاق، اشتقاق چپ‌گرد و راست‌گرد، پارس یا تجزیه، مسئله عضویت، ابهام در گرامرهای مستقل از متن و زبان‌ها 
• فصل ششم: ساده‌سازی گرامرهای مستقل از متن تبدیلات روی گرامرهای مستقل از متن، فرم‌های نرمال چامسکی و گریباخ، الگوریتم عضویت CYK 
• فصل هفتم: ماشین‌های پشته‌ای PDA ماشین پشته‌ای غیرقطعی، ارتباط بین زبان‌های مستقل از متن و ماشین‌های پشته‌ای، ماشین پشته‌ای قطعی و گرامرهای معادل آن‌ها 
• فصل هشتم: ویژگی‌های زبان‌های مستقل از متن خصوصیات بستاری زبان‌های مستقل از متن، تصمیم پذیری و خواص الگوریتمیک در زبان‌های مستقل از متن، لم تزریق زبان‌های مستقل از متن قطعی و خطی و روش‌های تشخیص یک زبان مستقل از متن 
• فصل نهم: ماشین‌های تورینگ ماشین تورینگ استاندارد، ماشین تورینگ پذیرنده و محاسبه‌گر، ترکیب ما‌شین‌های تورینگ، تز تورینگ 
• فصل دهم: انواع مدل‌های ماشین تورینگ نسخه‌های مختلف از ماشین تورینگ، تورینگ قطعی و غیرقطعی، تورینگ Universal، ماشین کراندار خطی 
• فصل یازدهم: دسته‌بندی زبان‌های صوری و آتوماتا زبان‌های بازگشتیREC و بازگشتی شمارش‌پذیر RE، مسئله توقف، گرامرهای بدون محدودیت و گرامرهای حساس به متن و زبان‌های مرتبط، سلسله مراتب چامسکی، خصوصیات بستاری، تصمیم پذیری و خواص الگوریتمیک زبان‌های REC وRE و CS، 
• فصل دوازدهم: محاسبه‌پذیری محاسبه پذیری و محاسبه ناپذیری، کاهش‌پذیری، قضیه رایس، کلاس‌های پیچیدگی محاسباتی