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

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