1　Chomskyの階層
1-1　正則文法
1-2　一般の文法
1-3　文脈依存言語
1-4　言語のクラス間の関係
1-5　演習問題
1-6　演習問題への解答
2　決定性文脈自由言語
2-1　DPDAの標準形
2-2　DCFLの補集合のもとでの閉包性
2-3　予知機械
2-4　DCFLの他の閉包性
2-5　DCFLの決定問題
2-6　LR(0)文法
2-7　LR(0)文法とDPDA
2-8　LR(k)文法
2-9　演習問題
2-10　演習問題への解答
3　言語族の閉包性
3-1　トリオと強トリオ
3-2　GSM(汎順序機械)写像
3-3　トリオに関するその他の性質
3-4　言語の抽象族
3-5　AFL演算の間の独立性
3-6　まとめ
3-7　演習問題
3-8　演習問題への解答
4　計算の複雑さの理論
4-1　定義
4-2　線型加速，テープ圧縮，テープ数削減
4-3　階層定理
4-4　計算量の測度の間の関係
4-5　移行補題と非決定性の階層
4-6　計算量の測度に関する一般的な性質：間隙定理，加速定理，和定理
4-7　公理論的な計算量の理論
4-8　演習問題
4-9　演習問題への解答
5　手におえない問題
5-1　多項式時間と多項式領域
5-2　いくつかのNP完全問題
5-3　補NP
5-4　PSPACE完全問題
5-5　TとNSPACE(LOG_n)に対する完全問題
5-6　手におえないことが証明可能ないくつかの問題
5-7　神託つきテューリング機械に対するT=NT問題：T=NTの成否を知るために必要なわれわれの能力の限界
5-8　演習問題
5-9　演習問題への解答
6　他の重要な言語
6-1　補助テープつきプッシュダウン・オートマトン
6-2　スタック・オートマトン
6-3　インデックス言語
6-4　成長システム
6-5　まとめ
6-6　演習問題
6-7　演習問題への解答