Iでは、有限オートマトンと正則表現、正則表現の性質、文脈自由文法、プッシュダウンオートマトン、文脈自由言語の性質、チューリング機械、決定不能性を扱っている。
IIでは、Chomskyの階層、決定性文脈自由言語、言語族の閉包性、計算の複雑さの理論、手に負えない問題、他の重要な言語。

手に負えない問題には、多項式時間と多項式領域、いくつかのNP完全問題、PSPACE完全問題などである。