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