可計算性與複雜性/簡介

本書旨在作為理論計算機科學中可計算性和複雜性主題的指南，面向中級本科生。它假設讀者對離散數學有一定的瞭解，並使用 Perl 作為所有示例程式的語言。

迄今為止，工作重點是形式語言，特別是喬姆斯基層次結構，以及與該層次結構相對應的機器。需要補充的主要領域是可歸約性部分，以及時間和空間複雜性部分。在喬姆斯基層次結構之外新增更多語言類別也會改進形式語言部分，並且在正則語言和上下文無關語言部分新增關於泵浦引理的資訊也會改進這些部分。