1　準備
1-1　文字列，アルファベット，および言語
1-2　グラフと木
1-3　帰納法による証明
1-4　集合
1-5　関係
1-6　本書の梗概
1-7　演習問題
1-8　演習問題への解答
2　有限オートマトンと正則表現
2-1　有限状態系
2-2　基本的定義
2-3　非決定性有限オートマトン
2-4　ε-動作を含む有限オートマトン
2-5　正則表現
2-6　2方向有限オートマトン
2-7　出力つき有限オートマトン
2-8　有限オートマトンの応用
2-9　演習問題
2-10　演習問題への解答
3　正則集合の性質
3-1　正則集合に対する反復補題
3-2　正則集合の閉包性
3-3　正則集合に対する決定手続き
3-4　Myhill-Nerodeの定理と有限オートマトンの最小化
3-5　演習問題
3-6　演習問題への解答
4　文脈自由文法
4-1　動機と導入
4-2　文脈自由文法
4-3　導出木
4-4　文脈自由文法の簡単化
4-5　Chomskyの標準形
4-6　Greibachの標準形
4-7　本質的に曖昧である文脈自由言語の存在
4-8　演習問題
4-9　演習問題への解答
5　プッシュダウン・オートマトン
5-1　直観的説明
5-2　諸定義
5-3　プッシュダウン・オートマトンと文脈自由言語
5-4　演習問題
5-5　演習問題への解答
6　文脈自由言語の性質
6-1　CFLに対する反復補題
6-2　CFLの閉包性
6-3　CFLに対する決定アルゴリズム
6-4　演習問題
6-5　演習問題への解答
7　テューリング機械
7-1　序
7-2　テューリング機械
7-3　計算可能な言語および関数
7-4　テューリング機械を構成するための技法
7-5　テューリング機械の変更
7-6　Churchの仮説
7-7　テューリング機械による数え上げ
7-8　基本モデルと同等な，制限されたテューリング機械
7-9　演習問題
8　決定不能性
8-1　問題
8-2　帰納的および帰納的可算言語の性質
8-3　万能テューリング機械と決定不能問題\r
8-4　Riceの定理と決定不能問題\r
8-5　Postの対応問題の決定不能性
8-6　TMの正しい計算と正しくない計算：CFLに関する問題の決定不能性を示す道具
8-7　Greibachの定理
8-8　帰納的関数論入門
8-9　神託計算
8-10　演習問題
8-11　演習問題への解答