مقدمه:
هدف از این درس آشنایی با نظریه محاسبات است که با ارائه مدلهای انتزاعی از ماشینها و کامپیوترها مسائل نظری جالبی مورد بررسی قرار می گیرد که اغلب معماگونه بوده و در علوم کامپیوتر کاربردهای فراوانی دارند. زبانها، گرامرها و ماشینها سه موضوع اساسی در این درس بوده و با بررسی زبانهای مختلف، گرامرهای مربوطه و ماشینهای انتزاعی مورد استفاده برای پردازش آنها معرفی می گردد. یک زبان صوری تجریدی از مشخصه های کلی زبانهای برنامه سازی است که شامل مجموعه ای از علائم و ساختارها است که قالب کلی جملات را تعیین می کنند. مبانی نظری مورد مطالعه در زمینه های مختلفی مانند طراحی و پیاده سازی زبانهای برنامه سازی، کامپایلرها، سیستمهای شناسایی الگو، پردازش زبانهای طبیعی و ... کاربرد دارند
منبع اصلی لاتین:
Introduction to Formal Languages & Automata 2nd 97 ; Peter Linz;
منابع فارسی:
مقدمه ای بر نظریه زبانها و ماشینها ، دکتر عبدالحسین صراف زاده، انتشارات ناقوس
نظریه زبانها و ماشینها؛ سودکمپ؛ ترجمه سید حجتالله جلیلی.
مقدمهای بر نظریه محاسبات؛ مایکل سیپسر؛ ترجمه محمدحسن شیرعلی شهرضا.
نظریه زبانها و ماشینها؛ انتشارات پوران پژوهش
سرفصل درس:
1. آتاماتاها، گرامرها و زبانها
2. آتاماتای محدود، گرامرهای منظم و زبانهای منظم
3. خواص بستاری زبانهای منظم
4. آتاماتی پشته ای، زبانهای مستقل از متن و گرامرهای مربوطه
5. نرمالسازی گرامرهای مستقل از متن و خواص زبانهای مستقل از متن
6. ماشین تورینگ و تز تورینگ
7. دسته بندی زبانهای صوری و ارتباط میان آنها
سرفصل ٢درس:
مفاهیم اولیه زبانها و ماشینها
DFA یا NFA و مسائل مربوط به آنها
زبانهای منظم و مسائل مربوط به آنها
عبارات منظم و ارتباط آن با زبانهای منظم
گرامرهای منظم و ارتباط آن اتوماتایی محدود
گرامرهای مستقل از متن و مسائل مربوط به آنها
اشتقاق و ابهام در گرامرها
اتوماتایی پشتهای
ماشین تورینگ
زبانها و گرامرهای حساس به متن
زبانهای بازگشتی و بازگشتی شمارش ؟؟
تصمیمپذیری برای زبانها
مسایل شمارا و ناشمارا
در گام بعدی لینک جزوات از این درس ارائه میشود
منتظر ما باشید
.
