فهرست مطالب
بخش اول: نظـریـه.
فصل 1 : مقدمهای بر نظریه محاسبات.
خلاصه فصل
1-1 مقدمات ریاضی و علامتگذاری مجموعهها..
2-1 سه مفهوم اساسی..
3-1 برخی کاربردها ..
فصل 2 : ماشینهای متناهی
خلاصه فصل.
1-2 پذیرندههای متناهی قطعی.
2-2 پذیرندههای متناهی غیرقطعی..
فصل 3 : زبانهای منظم و گرامرهای منظم.
خلاصه فصل
1-3 عبارات منظم.
3-2 ارتباط بین عبارات منظم و زبانهای منظم.
3-3 گرامرهای منظم..
فصل 4 : خواص زبانهای منظم.
خلاصه فصل.
4-1 خواص بستاری زبانهای منظم..
4-2 سؤالات مقدماتی درباره زبانهای منظم.
4-3 تشخیص زبانهای غیرمنظم.
فصل 5 : زبانهای مستقل از متن.
خلاصه فصل...
5-1 گرامرهای مستقل از متن.
5-2 تجزیه و ابهام..
5-3 گرامرهای مستقل از متن و زبانهای برنامهنویسی
فصل 6 : سادهسازی گرامرهای مستقل از متن و شکلهای نرمال.
خلاصه فصل...
6-1 روشهای تبدیل گرامرها..
6-2 دو شكل نرمال مهم...
6-3 یک الگوریتم عضویت برای گرامرهای مستقل از متن..
فصل 7 : ماشینهای پشتهای
خلاصه فصل.
7-1 ماشینهای پشتهای غیرقطعی....
7-2 ماشینهای پشتهای و زبانهای مستقل از متن
7-3 ماشینهای پشتهای قطعی و زبانهای مستقل از متن قطعی.
7-4 گرامرهایی برای زبانهای مستقل از متن قطعی
فصل 8 : خواص زبانهای مستقل از متن.
خلاصه فصل.
8-1 دو لم تزریق
8-2 خواص بستاری و الگوریتمهای تصمیمگیری برای زبانهای مستقل از متن
فصل 9 : ماشینهای تورینگ.
خلاصه فصل.
9-1 ماشین تورینگ استاندارد.
9-2 ترکیب ماشینهای تورینگ برای انجام وظایف پیچیده.
9-3 تز تورینگ.
فصل 10 : مدلهای دیگر ماشینهای تورینگ
خلاصه فصل.
10-1 گونههای جزئی در زمینه ماشین تورینگ
10-2 ماشینهای تورینگ با حافظه پیچیدهتر.
10-3 ماشینهای تورینگ غیرقطعی
10-4 یک ماشین تورینگ عمومی.
10-5 ماشینهای کراندار خطی.
فصل 11 : سلسله مراتبی از زبانهای رسمي و ماشینها.
خلاصه فصل
11-1 زبانهای بازگشتی و شمارشپذیر بازگشتی.
11-2 گرامرهای بدون محدودیت
11-3 گرامرها و زبانهای حساس به متن.
11-4 سلسله مراتب چامسکی.
فصل 12 : محدودیتهای محاسبات الگوریتمی
خلاصه فصل
12-1 برخی مسائلی که نمیتوانند توسط ماشینهای تورینگ حل شوند
12-2 مسائل تصمیمناپذیر برای زبانهای شمارشپذیر بازگشتی.
12-3 مسئله پس تناظر
12-4...مسائل تصمیمناپذیر برای زبانهای مستقل از متن.
12-5...موضوع کارآیی..
فصل 13 : مدلهای دیگر محاسبات.
خلاصه فصل..
13-1 توابع بازگشتی..
13-2 سیستمهای پست
13-3 سیستمهای بازنویسی...
فصل 14 : مقدمهای بر پیچیدگی محاسباتی...
خلاصه فصل..
14-1 کارآیی محاسبات....
14-2 ماشین تورینگ و پیچیدگی...
14-3 خانوادههای زبان و ردههای پیچیدگی...
14-4 طبقههای پیچیدگی P و NP.
14-5 برخی مسائل NP.
14-6 کاهش در زمان چند جملهای..
14-7 تمامیت NP و یک مسئله باز..
بخش دوم: کاربردها..
فصل 15 : کامپایلرها و تجزیه...
خلاصه فصل..
15-1 کامپایلرها...
15-2 تجزیه بالا به پایین در برابر پایین به بالا...
15-3 تابع FIRST..
15-4 تابع FOLLOW.
فصل 16 : تجزیه LL
خلاصه فصل.
16-1 تبدیل گرامر مستقل از متن به ماشین پشتهای غیرقطعی..
16-2 الگوریتم تبدیل گرامر مستقل از متن به ماشین پشتهای غیرقطعی برای تجزیه LL..
16-4 الگوریتم تجزیه LL(1).
16-5 تجزیه LL(k).
ضميمه الف: تراگذرهاي حالت متناهي.
الف-1 یک چهارچوب عمومی.
الف-2 ماشینهای میلی..
الف-3 ماشینهای مور..
لف-4 معادل بودن ماشینهای مور و میلی.
الف-5 کمینهسازی ماشین میلی.
الف-6 کمینهسازی ماشین مور...
الف-7 محدودیتهای تراگذرهای حالت متناهی
ضميمه ب: PALFJ : یک ابزار مفید.
جوابها: راهحلها و نکاتی برای تمارین انتخابی.
مراجع برای خواندن بیشتر.