کتاب مقدمه ای بر نظریه زبان ها و ماشین ها

فصل اول : مقدمه‌ای بر نظریه‌ی محاسبات 1-1 . مقدمات ریاضی و مجموعه‌ها 1-2 . سه مفهوم اساسی 1-3. چند کاربرد* فصل دوم : ماشین‌های متناهی 2-1. پذیرنده‌های متناهی قطعی 2-2. پذیرنده‌های متناهی غیر قطعی 2-3. هم‌ارزی پذیرنده‌های متناهی قطعی و غیرقطعی 2-4.کاهش تعداد حالت‌ها در ماشین‌های متناهی* فصل سوم : زبان‌های منظم و گرامرهای منظم 3-1. عبارات منظم 3-2. ارتباط بین عبارات منظم و زبان‌های منظم 3-3. گرامرهای منظم فصل چهارم : ویژگی‌های زبان‌های منظم 4-1. ویژگی‌های بستاری زبان‌های منظم 4-2. سوالات مقدماتی درباره‌ی زبان‌های منظم 4-3. شناسایی زبان‌های نامنظم فصل پنجم : زبان‌های مستقل از متن 5-1 . گرامرهای مستقل از متن 5-2 . تجزیه و ابهام 5-3 . گرامرهای مستقل از متن و زبان‌های برنامه‌سازی فصل ششم: ساده‌سازی گرامرهای مستقل از متن و شکل‌های نرمال 6-1 . روش‌های تبدیل گرامرها 6-2 . دو شکل نرمال مهم 6-3 . الگوریتم عضویت برای گرامرهای مستقل از متن* فصل هفتم : ماشین‌های پشته‌ای 7-1. ماشین‌های پشته‌ای غیرقطعی 7-2. ماشین‌های پشته‌ای و زبان‌های مستقل از متن 7-3. ماشین‌های پشته‌ای قطعی و زبان‌های مستقل از متن قطعی 7-4. گرامرهایی برای زبان‌های مستقل از متن قطعی* فصل هشتم : ویژگی‌های زبان‌های مستقل از متن 8-1 . دو لِم تزریق 8-2 . ویژگی‌های بستار و الگوریتم تصمیم‌گیری برای زبان‌های مستقل از متن فصل نهم : ماشین‌های تورینگ 9-1. ماشین تورینگ استاندارد 9-2. ترکیب ماشین‌های تورینگ برای کارهای پیچیده 9-3. تز تورینگ فصل دهم : مدل‌های دیگر ماشین‌های تورینگ 10-1. تغییرات جزیی در طرح ماشین تورینگ 10-2. ماشین‌های تورینگ با حافظه‌ی پیچیده‌تر 10-3. ماشین‌های تورینگ غیرقطعی 10-4. ماشین‌های تورینگ جهانی 10-5. ماشین کران‌دار خطی فصل یازدهم : سلسله مراتب زبان‌های صوری و ماشین‌ها 11-1. زبان‌های بازگشتی و شمارش‌پذیر بازگشتی 11-2. گرامرهای بدون محدودیت 11-3. زبان‌ها و گرامرهای حساس به متن 11-4. سلسله مراتب چامسکی فصل دوازدهم: محدودیت‌های محاسبات الگوریتمی 12-1. مسأله‌هایی که نمی‌توانند با ماشین تورینگ حل شوند 12-2. مسأله‌های تصمیم‌ناپذیر برای زبان‌های شمارش‌پذیر بازگشتی 12-3. مسأله‌ی تناظر Post 12-4. مسأله‌های تصمیم‌ناپذیری برای زبان‌های مستقل از متن 12-5. پرسشی درباره‌ی کارایی فصل سیزدهم : مدل‌های دیگر محاسبات 13-1. توابع بازگشتی 13-2. سیستم‌های Post 13-3. سیستم‌های بازنویسی فصل چهاردهم : مروری بر پیچیدگی محاسباتی 14-1. کارایی محاسبات 14-2. مدل‌های ماشین تورینگ و پیچیدگی 14-3. خانواده‌ی زبان‌ها و دسته‌های پیچیدگی 14-4. دسته‌های پیچیدگی P و NP 14-5. بعضی از مسأله‌های NP 14-6. کاهش زمان چندجمله‌ای 14-7. کامل‌بودن NP و پرسش باز پیوست الف : تراگذر‌های متناهی الف-1. چارچوب کلی الف-2. ماشین‌های میلی الف-3. ماشین‌های مور الف-4. هم‌ارزی ماشین میلی و مور الف-5. کمینه‌سازی ماشین میلی الف-6. کمینه‌سازی ماشین مور الف-7. محدودیت‌های مبدل‌های متناهی پیوست ب : معرفی نرم‌افزار JFLAP پاسخ‌ها: جواب و رهنمودهایی برای تمرین‌های انتخابی